# -*- coding: utf-8 -*-

"""剑指 Offer II 115. 重建序列
给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。

例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。
如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。

示例 1：
输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
输出：false
解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。

示例 2：
输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。

示例 3：
输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出：true
解释：最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列：[1,2,3]。
序列 [1,3] 是它的一个子序列：[1,2,3]。
序列 [2,3] 是它的一个子序列：[1,2,3]。
因为 nums 是唯一最短的超序列，所以返回true。

提示：
n == nums.length
1 <= n <= 104
nums 是 [1, n] 范围内所有整数的排列
1 <= sequences.length <= 104
1 <= sequences[i].length <= 104
1 <= sum(sequences[i].length) <= 105
1 <= sequences[i][j] <= n
sequences 的所有数组都是 唯一 的
sequences[i] 是 nums 的一个子序列"""


class Solution:
    """反过来考虑，一队子序列的最短超序列，不就是以子序列成图，这个图的拓扑排序吗？
    而这个最短超序列还要保持唯一性，那不就是拓扑排序的每一步入度为0的节点仅有一个，且为提供的数组相应位置数字。
    
    需要注意一点，这道题无论从数组还是子序列都没有说数字的唯一性，所以并不能直接按数字值作为顶点来建图。而数组肯定是个超序列，所以可以用数组来制作顶点。
    最好将值转化为id来处理。
    
    在拓扑排序时，建立起点节点队列，有效提高效率。而不是每次去取入度为0的节点。"""
    def sequenceReconstruction(self, nums: list, sequences: list) -> bool:
        # 数组和子序列都只有一个
        if len(nums) == 1 and len(sequences) == 1 and len(sequences[0]) == 1 and nums[0] == sequences[0][0]:
            return True

        vertexs, temp = [], dict()
        for i in range(len(nums)):
            _id = 'n'+str(i)
            vertexs.append(_id)

            if nums[i] in temp.keys():
                temp[nums[i]].append(_id)
            else:
                temp[nums[i]] = [_id,]

        graph, indegree = dict(), dict()

        # 建图
        for subseq in sequences:
            i = 0
            while i < len(subseq)-1:
                pre_v, next_v = subseq[i], subseq[i+1]
                for _pre in temp[pre_v]:
                    for _next in temp[next_v]:
                        if _pre in graph.keys():
                            graph[_pre].add(_next)
                        else:
                            graph[_pre] = set([_next,])

                        if _pre not in indegree.keys():
                            indegree[_pre] = 0

                        if _next not in indegree.keys():
                            indegree[_next] = 0
                i += 1

        # 计算入度
        for nextSet in graph.values():
            for _next in nextSet:
                indegree[_next] += 1

        # print(vertexs)
        # print(graph)
        # print(indegree)
        p = 0
        zero_in = list(filter((lambda k: True if indegree[k] == 0 else False), indegree.keys()))
        while zero_in:
            if len(zero_in) == 1 and zero_in[0] == vertexs[p]:
                # indegree.pop(zero_in[0])
                _zero = zero_in.pop()
                if _zero in graph.keys():
                    for _next in graph[_zero]:
                        indegree[_next] -= 1
                        if indegree[_next] == 0:
                            zero_in.append(_next)
                p += 1
            else:
                return False    # 有环

        if p < len(vertexs):
            return False    # 长了
        
        return True

if __name__ == '__main__':
    print(Solution().sequenceReconstruction(nums = [1,2,3], sequences = [[1,2],[1,3]]))
    print(Solution().sequenceReconstruction(nums = [1,2,3], sequences = [[1,2]]))
    print(Solution().sequenceReconstruction(nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]))
    print(Solution().sequenceReconstruction(nums = [4,1,5,2,6,3], sequences = [[5,2,6,3],[4,1,5,2]]))
    print(Solution().sequenceReconstruction([756,6966,700,3608,3142,4079,7612,5261,1373,3983,4149,8637,2071,7988,4204,2922,5866,5224,8085,9253,6680,3099,4547,4667,6016,3516,2409,3648,8176,7909,205,5531,9446,6815,7317,1074,4247,8205,6637,284,3166,8537,9566,817,1278,1743,9725,3799,8090,6844,3284,8382,8204,2897,9970,6794,3129,3554,9054,4365,3873,3453,6208,2091,7078,1668,1445,4540,6205,1791,431,2752,3477,7189,2438,8460,4181,9305,9644,2041,7782,441,4976,685,1082,159,2626,371,6077,2887,8839,365,9205,7313,9382,1081,4879,1922,1862,6718,941,7570,3812,5736,4241,993,4625,3649,1702,3609,5267,8587,4012,1279,2581,7703,1823,4713,5356,1355,7859,6812,6980,1314,9084,1669,5882,3306,8012,5892,2819,6945,3785,452,166,6381,8003,8052,1612,8115,9652,9532,9198,9386,8048,8288,7114,9666,602,9451,4137,3550,9025,9891,651,7057,4142,334,702,5381,2285,1441,3565,3579,6770,6621,4550,3366,7423,4482,1544,8842,1191,5229,4753,7186,8593,5937,9593,3905,5631,4895,9243,490,8270,1719,6828,4140,6625,6956,7608,2955,4767,7302,1964,716,9437,9536,8763,904,1397,5867,3021,695,7142,7126,9181,6654,6903,6496,8877,1703,6626,5269,3234,7886,6607,8446,4590,6687,4220,9967,4577,9290,4878,7358,6639,1036,2532,9475,3730,2667,5390,2963,3779,3399,2668,4754,7946,1924,1813,2838,7308,3037,3724,5082,2599,6996,4428,2274,1118,9776,2012,9029,8407,6198,5648,3705,988,9612,6116,6888,8207,8626,9984,6565,9170,7120,2009,5481,107,5976,8946,6083,6152,3926,6249,1861,9171,7741,7815,5813,1991,837,4827,6551,2634,3246,757,8179,8071,2789,9141,6701,9591,6226,3493,907,5967,877,9736,767,5164,1097,2845,1065,825,8075,7469,1809,742,675,2746,6857,2116,4110,3839,4828,9617,9065,4529,7721,569,7718,976,4657,2213,2785,4718,3165,6384,3423,1004,9911,8564,8904,1269,9657,5938,5398,337,1765,3632,1747,5450,2616,2669,5546,9483,5302,7052,5770,1044,1540,8730,6647,7750,9184,6511,5153,6025,9056,4691,7044,6723,8190,9824,10000,5462,8905,646,5525,3803,3027,8801,1225,3036,8393,2431,2615,9935,8228,8505,4246,3044,8989,6399,6261,2327,1981,1459,7943,9026,7635,3783,9719,7958,2192,9108,6121,2436,3798,256,1296,4994,7426,6106,247,4356,4517,1121,3822,7384,8301,8046,7259,3043,8309,2778,8253,9704,1671,3970,7334,8919,5385,3613,3711,5131,410,726,148,4675,1241,8691,4983,123,5397,3146,70,2735,2816,9043,9540,4371,212,4647,879,3065,1532,6806,5373,9044,5663,6985,7073,883,6981,4392,5877,6968,5916,9284,7036,7757,7418,9030,6559,5944,9491,501,1105,1761,9838,1740,1356,1681,3135,1640,2174,8668,697,2692,1526,7637,4527,537,5496,3320,2574,6513,3483,6592,7102,3773,9884,5495,8503,731,1623,2345,3861,592,3590,5289,4481,1548,9185,8417,770,5472,515,9729,6334,2522,8440,8364,8334,189,4819,4973,454,253,1897,1228,3046,7778,6901,9174,6048,3740,5009,9061,4679,8125,9676,3242,2169,7378,9938,2188,7483,3768,6805,3318,4152,8022,5303,1881,1506,871,1137,2461,7173,393,3127,508,3676,1039,3928,7260,6204,2714,7280,805,9934,6643,4065,8844,9060,3062,440,5139,7321,4458,7238,4253,405,6756,3927,868,4424,2475,815,2656,1729,6870,814,9560,8439,1957,3921,8019,8806,3762,5751,4870,3973,4283,9737,4798,7131,6700,586,9564,939,785,2834,8964,8203,7431,3467,3682,7993,6445,3581,9391,1038,9830,2384,1094,3869,8967,2372,4307,1234,6355,5678,196,5898,3251,4989,298,1591,855,8217,9476,7425,8875,273,2926,8822,8108,2712,2045,8792,7594,7253,6886,6619,319,4466,5402,6425,3288,1174,3804,7080,2109,3793,4353,3837,9505,1446,4537,5876,5395,5238,1830,8772,7780,8530,1768,6736,8535,954,2017,3392,1802,7406,7165,8887,7532,4069,3617,3885,2577,5784,9251,4193,9778,4147,2190,4809,2736,6395,3593,4559,6671,9332,5268,6481,1333,3794,2125,1531,3124,6486,1578,7233,1077,7007,3441,3645,1371,9479,8337,8051,5279,9892,9851,4868,5735,2414,1110,851,9220,4715,4542,3068,259,8374,4477,2896,3482,8526,5698,5671,456,8573,869,2176,2833,1020,5200,8039,246,7822,4360,2374,5252,8556,3548,2312,8809,5337,7397,1235,1998,3323,9609,9223,1187,6704,8327,5180,1511,5479,5587,2863,6313,5618,5497,1109,4135,7512,4849,3597,6531,6562,6165,9562,9067,9682,1185,5501,30,236,3388,551,5844,4437,6662,6954,4768,4382,5649,5681,7712,2087,388,9762,4864,5726,8985,4563,3906,3862,7582,8866,3854,383,7792,8010,5056,2883,7518,7995,9225,8088,1603,1113,4756,9810,506,1721,9790,2855,1407,2539,3462,3933,3181,4378,2768,4148,399,7576,9455,488,3075,6451,3118,7825,1607,8930,6742,3578,2964,2953,9876,6776,8502,5230,9050,3131,3990,280,4128,1557,3786,9104,7282,5024,6606,5427,9886,4513,9573,4522,2352,2740,4233,8156,4695,4343,3450,5023,1745,5486,9607,8585,8222,2872,8954,9507,739,2608,8419,5221,1002,4800,1211,1217,7752,4445,1402,5896,4010,5584,5940,4689,8229,7670,511,5507,9803,7888,9936,6837,3690,9028,5519,7353,2558,7875,2033,6923,2419,6098,3826,8620,5015,9917,8880,7083,7028,9689,9954,6480,6282,7971,3034,6110,3221,5741,3916,491,6065,7084,7127,5575,6457,672,1505,8077,4783,5864,2228,704,3200,7158,2439,186,8903,8962,661,5860,4435,6604,6703,9594,329,1599,1584,8516,7091,294,8812,696,4295,5683,7716,7473,7851,9235,9343,3531,9117,3533,7407,9706,561,3014,6807,5756,3801,5766,2888,8244,1057,2378,4981,9372,9590,1084,175,9850,7022,4317,68,6189,3582,3179,39,5854,4701,8727,609,1129,2498,9974,3312,3833,5626,1829,2952,709,7676,1061,5194,6629,6275,4586,5245,3750,9933,4414,3340,1818,5959,4336,1716,9601,2484,3864,7029,4448,4112,6070,5943,5760,1098,4053,7689,8058,4545,8598,6129,6878,4488,5266,1398,3387,6332,5432,6007,1938,2366,1214,3201,2180,1959,2809,5199,3532,8579,6215,9902,6394,3446,3716,3028,6716,889,2337,5133,6408,3307,7788,8981,8164,1708,521,3707,7735,8471,4853,9335,898,4144,7458,8254,7056,710,8588,4346,7602,8468,2902,5985,4035,2748,7824,370,4461,3132,1138,7071,3473,5767,5033,9208,1549,3297,2595,9176,4217,2407,5954,3051,974,2020,7289,7228,6068,6040,4131,9129,7019,4250,5504,2552,8908,6537,9492,2270,7953,4420,9880,5987,3436,8038,8262,4922,1159,7219,5482,1676,4462,1204,6664,1744,5089,2322,418,4789,8252,8145,7023,611,6037,4331,8847,75,5484,156,6589,3728,8094,5836,6767,8943,4772,8273,3890,5800,6227,7288,2648,4438,996,3721,5647,5241,5107,8295,4139,3541,7435,6086,1265,7890,6796,6091,5748,3113,6372,744,8406,3971,1973,4737,3463,2275,6561,4920,7041,5611,6761,6835,2876,9755,3925,2744,9788,9101,7118,4038,5889,849,9285,8864,2700,250,2110,8768,2254,5543,3749,1421,1927,3445,3095,9038,8640,858,719,9258,1229,2417,3918,4150,4293,8860,4838,564,7536,6898,6713,1382,8728,5568,9820,5550,3693,1575,7853,4474,9450,7830,6117,5282,6706,8717,4441,6474,9761,9216,2914,1209,4263,8426,3536,6914,109,935,4078,8161,6823,4066,5053,6798,9734,9950,8995,761,607,6294,1515,5456,9460,2993,1058,179,6612,1485,5408,5567,8015,7584,1963,4843,4557,3287,9635,9207,6690,3138,7685,6452,231,6344,8750,1835,8741,7008,5614,959,8858,9500,6276,255,2077,1509,5977,4285,3944,6757,5934,1075,9276,7970,9796,1232,9798,5704,4453,2749,6461,7357,7832,1470,8932,6441,5121,5360,2106,2997,7234,8232,1056,6715,6176,7329,1150,4573,1885,8836,2202,4936,2138,8888,1079,9545,7220,8991,6133,936,5551,2705,5975,6557,2977,5105,9919,6390,4497,4898,8829,3010,2610,7930,6273,7745,5592,1030,4061,6290,6978,4342,309,7755,5215,449,4067,737,1175,3542,8401,9745,934,1404,34,6730,1063,727,1713,6217,1353,7623,759,473,9201,5969,8134,5835,7468,1091,694,5405,8470,3672,623,1472,7659,9533,6376,8185,4641,1533,6656,8381,5644,5154,6370,7293,349,1380,8923,5091,235,3015,8320,3335,4219,4663,8189,1687,7239,2282,6406,5248,812,7910,3500,8119,9143,2303,1096,1300,2938,4054,9495,8367,3249,2954,9493,9525,9489,5254,12,8922,4974,2454,9577,5527,4804,8078,3923,9508,1711,5187,8216,5329,1250,1872,9524,3726,4042,7997,2292,9550,6292,7402,614,3418,6556,2112,3301,51,1858,1308,2078,2237,1789,913,9897,3847,4230,3904,9610,8347,5364,9358,7866,9678,2072,9980,3330,3555,7420,4323,9895,3348,8633,7530,2875,8420,3372,5921,1954,890,2479,9696,2535,4762,5628,2336,1839,7364,133,7942,8782,6162,262,448,2678,6871,1670,2194,7662,6134,3262,7744,7885,8453,4192,7454,4932,4728,6801,7809,2629,9153,2761,150,2480,3725,7107,2985,9213,6335,8281,5051,3128,9345,6353,7235,8731,5335,1331,7571,1454,7972,3108,5052,7167,2525,8340,3290,122,6200,3534,8298,6244,6119,5547,633,5524,2256,4490,1817,4060,9232,8350,4925,2502,3765,7786,3902,4519,779,5444,8827,7891,5883,2860,5670,730,7363,1856,4830,1491,78,2005,3857,9943,8428,6210,2830,9552,1297,1266,2184,1416,821,226,9496,2762,1348,2031,4524,3628,6576,7660,6245,4840,4518,830,7858,9786,1378,5588,77,4235,5821,6915,2309,1772,80,6651,1140,5094,292,7445,5321,2747,5485,5146,6301,113,3302,8230,4923,8043,4422,958,615,9018,5071,2000,7320,604,3273,5763,4816,8414,9010,2516,3078,621,5379,2179,6751,3684,5980,6917,6302,8394,7860,566,4017,2524,2975,3271,6135,4784,652,9570,6413,14,916,5630,3054,380,2625,6635,5744,4861,7377,793,7926,6887,4468,6150,3603,6338,436,6482,9659,2517,1381,5468,4751,8356,3508,9339,3722,9966,89,3294,4726,7770,3112,3289,2302,6179,6596,1958,6737,3491,6997,6611,2361,1484,3584,8174,7835,5779,1636,2584,7491,3466,2652,9307,1784,9556,1120,2528,7184,7719,2644,170,5150,180,2404,1301,3111,7529,3653,2688,3969,2501,8202,8224,5293,572,1576,7038,1369,8933,6739,7865,4971,644,1780,950,6428,3819,5186,981,5669,283,7516,3501,1170,2286,9374,7159,717,1487,2602,9082,2538,7933,2619,8092,3984,6127,6930,2353,5870,9466,8061,7146,2962,1620,8567,594,9152,1224,6264,8649,94,6550,4653,6728,9331,2211,6953,2701,6122,4883,4769,9260,4627,8988,3069,9627,6839,9504,9998,3120,4085,5025,6349,6087,1580,3202,8786,4580,4501,7590,7606,9180,7626,5816,8600,1840,9797,4427,1486,4334,7720,3422,714,8324,3702,5210,1428,5176,650,8889,469,395,1236,2107,4377,4354,7257,964,9252,6564,6834,5984,9781,8669,2805,9888,6830,6910,9801,72,4937,9945,1059,1341,8135,928,606,3186,9013,3188,1177,3620,7641,5088,7791,2141,5115,927,6188,2545,7460,5540,6004,1563,715,1216,5204,8445,7178,3416,7793,2646,1558,4865,9031,6319,6185,8540,9110,626,5570,2462,1379,8141,1565,8219,3141,8342,5393,7027,5351,922,2415,2899,8744,6983,6437,1083,7205,5571,4678,9237,4120,1757,8149,3377,736,8319,7595,8983,3706,1376,876,6771,7366,4115,7211,7535,5166,1219,3383,2018,1263,5765,6383,9125,6971,3332,1116,1344,7349,7385,211,6307,5586,4671,9000,1130,4687,6415,3226,6235,8218,7284,8220,4416,3545,8604,3842,6328,2732,4423,9529,2021,5538,3811,6354,1173,9336,5319,1414,3431,8056,323,903,943,3876,7732,5737,8499,8021,1860,9464,755,7155,8977,5865,3713,1824,2707,5185,6363,1408,9267,1014,9777,6792,4182,8353,2089,4359,2739,476,562,7604,3352,6526,3570,9430,5577,2927,2974,4698,3995,3360,1041,229,8234,4602,1049,6509,6054,7756,3892,3055,6889,8448,3264,1929,3435,7388,2460,9991,7447,4271,8380,8424,5873,8756,258,411,1975,2451,593,2348,7318,7588,6396,6145,1919,9302,8752,5087,1067,489,3472,8333,4107,1154,4116,2208,4363,6193,9311,772,3103,3430,7963,8555,3771,9023,9204,3469,1985,97,2995,9602,9640,576,1391,3407,2885,5336,5890,6028,7034,8275,6180,1680,834,8775,7774,6928,2765,5761,4943,3671,5729,2478,6694,8079,9735,3530,7800,7775,1996,1362,492,5143,4143,6967,4473,6774,2356,2573,8383,4195,8805,5378,4918,3920,8385,6051,4269,6925,3045,7443,1338,9506,7545,6279,8389,4419,516,287,4628,9813,4014,4834,6440,645,2471,3317,373,9392,4188,5313,5141,5197,1193,3853,1145,1363,5433,4643,6156,6062,3882,6254,4705,233,118,5728,3060,2505,3225,3930,5627,9172,4866,1248,3459,192,3644,9244,1581,2837,7771,7191,422,4630,5298,7387,4582,363,5434,7787,5903,4358,1825,6505,1496,5280,656,1550,1905,2343,6572,9203,4738,9840,2458,5557,4719,9024,6883,5695,7581,1375,2591,1200,8467,1928,590,5286,2035,1628,3938,5157,7561,3155,7932,8663,7463,1326,3566,3601,8907,416,9951,1865,4352,4118,2499,3710,596,7684,6347,531,8582,8733,9989,1560,9145,7965,7207,6216,3962,2330,9086,2725,984,8843,1810,9605,3748,1171,2846,3631,6546,3936,5927,9833,8194,171,6993,1283,3643,2411,3151,3022,3535,9112,1672,4616,4425,4274,4183,6724,382,5555,9288,7398,3668,1160,1165,873,8594,2301,4857,4158,529,6685,324,8699,5755,6074,1208,1405,3680,4917,8770,3254,2886,366,9539,5981,643,2310,2998,2129,9702,3223,3003,9107,544,2724,7255,3758,4309,2578,3324,3807,5013,497,6444,9133,332,9137,4095,2820,3718,657,8883,8703,5092,8893,9968,4380,3248,3823,802,3238,9375,8318,4608,3351,7333,7873,354,2155,4194,1323,7753,1967,6818,4520,6029,3397,3255,8987,5566,9228,2511,4236,799,4670,4262,1833,7979,7277,9312,2483,2421,4319,7043,9976,6239,9291,2305,9606,1874,4335,6605,7501,2066,10,546,1965,4259,3502,8208,1748,5986,857,8978,4787,6961,442,7924,3968,1852,2793,8664,8918,4109,6240,624,4912,8404,9905,6207,138,1504,6669,3067,2287,5509,6745,6754,3032,7351,2132,47,2340,7985,1125,6911,2375,6860,7931,2931,5037,7365,2218,4072,6521,1328,4044,2600,9093,2166,4652,6554,8971,4730,3031,7839,4240,7826,7229,8293,5822,4841,7035,6143,6986,5694,8525,7273,8451,2630,3778,1626,7643,8355,4977,364,3136,6401,4739,7949,4412,5247,8591,7459,5848,2868,908,7821,6031,1111,8687,4231,1409,3703,4284,8314,5583,3891,8013,5192,9140,7031,2582,8508,6658,587,1535,9501,6182,4242,8666,2159,8996,4373,9642,1218,6470,914,4213,8787,157,5118,7408,2371,7451,5511,4433,7360,503,6775,5029,3756,2199,5503,9158,3941,765,559,8681,6096,6780,135,618,8632,6840,1133,7596,7012,9314,6553,3742,5852,4869,6030,9406,2958,5191,4184,4664,8507,5255,2219,8104,8469,1047,2365,2469,9132,3592,8547,1588,9062,3097,478,6181,2877,9351,8698,3625,8372,2737,29,8376,3204,9695,1904,4151,911,338,8870,6327,6186,7845,6460,8961,9629,9510,2376,4773,19,6566,5404,8490,7849,3551,7389,952,6356,1222,4847,2513,4320,9615,2844,1009,5235,4945,577,968,5079,7593,9002,2269,5190,987,9961,2537,9932,2570,9142,6242,7119,5123,5858,6922,5742,8427,5034,9494,9847,8825,9051,2930,7544,9274,5011,7852,2115,2874,8520,5613,5792,8396,1060,517,203,1361,2784,9325,3717,3844,3413,9150,6043,1357,6291,2643,6219,7609,5842,4051,5036,662,8118,3479,7484,5260,403,206,7962,7874,8675,5654,3841,3220,8910,9197,8838,5919,7301,2946,513,7794,2772,9878,1354,9472,6371,1769,8496,5775,4740,8484,9600,2426,9832,4877,5168,6974,7784,5064,6927,7605,3084,4812,6764,3268,8017,7668,5526,5285,6822,1596,290,5978,1804,8378,5272,1006,361,7923,6691,3293,9378,4315,4016,2766,7564,9622,6183,2064,8949,6050,1389,8370,9263,6851,3546,8157,4460,5574,318,472,6573,3006,1878,4836,9004,7039,6836,8494,1052,3217,7812,8715,6352,3775,6101,2095,202,4032,1953,8379,920,6095,9366,9478,6105,5606,1706,5642,6109,7428,7587,9040,3449,2120,725,2704,9259,7286,1728,2060,6270,2873,9693,8142,1519,8329,7887,2496,881,9447,6485,8237,5085,2338,4750,3651,3840,768,1536,3767,33,1990,3442,210,1315,356,5500,3835,4097,2102,8722,864,2200,4631,2620,6600,4712,6293,7710,7531,6247,9070,1863,7558,3963,4610,4666,832,1477,5680,3846,2989,1583,8146,1155,9941,639,1553,8483,6055,4521,8631,55,3259,1051,1106,7537,8297,2255,409,8031,3305,6009,2123,5213,5508,978,4910,6727,6826,2006,3206,5464,5532,8481,3398,4500,7202,5304,5807,254,2290,7654,4988,3611,8865,9667,100,9022,1212,7955,7727,2140,6234,2769,5018,8124,3415,3522,1099,6497,7209,5634,6431,3575,2622,5556,7709,5193,9699,9587,5925,8937,5465,4959,7729,8832,8392,3090,2661,2410,7151,3635,8138,3130,7247,3967,4622,2325,6487,5513,8570,6558,679,8726,8638,1617,3148,2675,5605,5805,7412,4961,4549,8611,4614,4098,3513,9246,5108,3092,7370,5974,9837,7467,5382,2994,4950,1561,7136,4607,3056,6919,8400,9774,6677,9079,9077,3316,5788,3986,4348,875,862,787,9319,6236,6858,5473,828,5443,4673,9722,7221,3074,4656,413,9873,9369,1851,9939,2978,2182,774,2554,8005,4512,6904,5692,4953,6525,5841,617,778,5288,5651,4899,2272,4757,4275,7004,6251,4919,5239,2854,6046,6571,658,28,1564,9294,4592,5438,797,4452,5306,4034,2982,6161,5271,4588,7153,1490,1700,9860,4574,412,446,7448,41,4661,2030,2703,7917,7810,3852,3845,7456,632,2402,8680,2904,2757,831,5746,5294,5043,8998,3199,3083,1962,1488,9149,7276,5960,2649,8952,8285,1893,1492,1892,8425,6752,7437,1141,9036,1586,9744,3856,5914,5163,3096,4587,3168,3911,4318,187,8628,4560,6066,4389,49,1272,1364,7457,4600,1827,8242,2923,1675,4636,4907,3633,6434,3573,631,8083,1335,807,3170,9199,3490,5829,2559,6026,7511,512,8688,4806,5387,1123,7848,2395,8821,994,8241,4795,2094,896,7586,6979,3908,1213,6545,8629,1473,9709,3236,1914,9523,9457,6692,2645,6892,6536,1451,5738,5515,2631,6762,9620,223,8619,1890,9660,2250,2206,6512,4451,9703,20,7452,1589,4406,540,7016,6579,6591,2261,5220,4221,8432,8250,7204,9650,6994,758,5084,8107,9194,3004,6540,1101,9675,6640,4094,8777,9616,9760,1089,291,3089,9035,7781,4340,7258,1012,6389,2441,1153,7986,9792,4122,6695,3210,5315,3901,1859,5625,3677,9988,8458,2858,2917,9793,4446,6698,3770,5826,9057,1429,3178,1029,6056,4041,3764,6977,8605,5440,182,2070,6734,538,5490,4649,3133,2760,7900,8289,2252,6111,1517,443,1801,872,6197,7206,7444,1635,1180,2086,4888,3123,6787,232,3020,4104,1704,8303,6519,7691,9875,4690,1759,2052,2240,359,3139,9927,7999,2466,3738,9928,6449,6153,191,4483,102,4658,7803,8531,9987,1645,4960,9718,5007,4722,5899,6747,2422,6577,2548,6283,9538,1732,8140,317,6053,3258,708,4724,6358,1124,6522,2635,3025,5909,3769,9316,9663,8168,9977,6351,8360,1642,6697,2588,6410,6504,8026,556,5559,5667,3683,9066,2222,3621,4723,5806,5923,2856,2663,6006,5778,7200,6044,4604,4502,1430,3265,8053,3299,7079,9576,8121,1826,921,2379,1393,6861,3943,234,9175,6357,8853,698,3698,796,9078,9802,7323,4129,4125,1730,4260,9712,5307,6067,6361,2782,7677,1842,3455,7991,1587,1786,3744,625,7844,3484,4721,2959,4566,8869,7137,496,3512,3114,4214,321,6547,4325,2042,1941,4168,2294,9962,7319,7309,1249,7914,3485,5058,9975,5535,6141,4225,7672,4421,2400,4532,9016,6832,4507,8365,8569,8332,3125,3363,9299,7675,36,9411,4429,3105,4401,4025,6789,3737,5580,143,2062,3701,1997,6693,1921,8310,7682,9296,782,4781,8062,5287,7599,637,4374,4216,764,1466,1658,6281,404,7763,9445,8566,4954,2786,8576,1437,9114,4447,7823,7555,4418,6013,1663,7310,6337,8306,1352,6655,5904,3216,2446,8534,806,9393,3331,2246,5688,7630,8882,8766,4759,9859,9212,786,4030,3292,3480,272,7876,4829,4266,7399,5676,7901,4287,8349,4161,5077,6269,3641,1169,199,5429,7904,8437,6808,4842,8462,4434,2185,2236,4037,9756,1848,252,5657,848,5635,7504,5119,9262,1016,8267,8456,2212,7880,1816,8188,1223,4186,826,2613,5711,4008,8885,6490,2445,8612,2295,8783,88,9940,9417,9098,8572,9488,2278,1651,8348,8486,6343,466,6825,7742,1760,6132,5799,1673,18,2529,3140,4077,1901,749,2929,8028,164,5957,3903,4785,4000,8160,4856,9926,4546,8679,4699,5665,1205,7950,1714,9807,4609,3100,8595,5358,8,1276,5348,7337,8030,7069,6735,1541,7476,4361,842,421,8511,6409,5251,4364,4599,475,3650,899,9254,7000,207,7296,8684,3781,9156,3662,5810,7180,7254,5399,7694,9920,5370,1316,8037,2836,2032,6059,4040,2593,1340,7598,9821,9747,6534,2894,8909,1695,3900,4991,3033,7047,385,1424,5777,5330,4177,2826,5787,3966,2074,9426,7652,3224,8902,3365,8648,9592,3064,1164,6646,7042,8415,568,5510,1500,4896,3219,8116,4688,8592,6224,7591,1602,7747,9169,4467,1151,2432,6729,8574,5145,8796,3735,7508,2604,8667,3893,4632,3618,8007,9558,5781,8029,9081,8589,9011,9565,6924,784,2862,8339,7702,6949,5232,3406,2541,7552,6391,500,5002,4957,2774,6036,5375,8322,3282,4332,7169,1709,3960,7068,9281,6035,9266,7636,6942,4731,3116,8251,6803,3311,909,6705,2795,3478,9839,8510,3646,961,8536,9270,775,1017,1649,718,8422,6311,8036,4237,1290,2767,5840,3421,8129,6021,8321,6178,7569,8101,119,9713,3373,3848,8674,4650,4013,1303,195,3328,1805,4493,2492,5126,9819,1503,1122,7342,9555,4833,1422,5140,2865,5367,2913,9303,5132,1546,3559,3586,1977,2034,2394,3058,7,3167,6137,3496,6453,1513,2413,845,2612,6177,1467,2104,991,2203,6722,3954,3253,1821,2596,3404,7760,8412,8132,3101,3800,2638,605,7440,2424,6011,7327,5601,486,2543,5897,1877,458,5861,6429,6644,3230,7104,9923,4523,8074,7977,9947,1227,9764,8581,4541,841,2215,3456,390,2587,3896,4805,1168,9730,8656,7065,8148,4894,9794,2979,4921,9116,3026,5639,2280,9804,420,9727,811,810,9160,9490,1281,686,690,1895,1559,222,4931,54,2515,4872,627,4929,2390,9073,8596,1555,4169,6926,316,967,136,1311,2362,1610,1773,7433,5796,3338,6590,9214,1158,1611,7528,5859,6944,3759,2148,7367,3673,8571,955,4598,1070,1657,5045,4454,4027,4859,6464,314,2459,9467,7507,5218,149,4778,4639,9959,4871,2195,1686,7082,62,1838,4124,7455,8050,7982,891,1947,7954,560,4969,9885,2186,4114,3776,4629,2114,9268,6931,6342,6937,4386,7534,6847,5956,8409,9292,4646,6535,8645,9854,5717,2346,6483,4796,8034,111,9394,7560,8126,221,9330,137,1332,9549,4211,7256,5182,3539,5869,3184,1507,6382,8433,9921,3433,2601,1273,589,9135,9531,82,9346,6411,8665,910,9217,5710,1305,5212,8269,8336,2562,1139,2191,459,3457,5171,4185,1524,5713,9234,1737,3426,2957,265,3899,6252,7748,1917,781,6782,1955,2617,5135,7303,7701,8790,5311,906,8735,9048,2288,3828,3358,4803,677,1763,1048,3380,7894,4892,8282,598,7464,7300,8873,4591,7101,6912,8358,2810,341,9724,4083,1659,6093,5014,2628,7145,7481,3283,6124,1189,1001,4825,9387,2936,1178,391,2889,121,5263,5346,8707,8351,654,7807,5638,6679,8464,6147,5291,6374,603,7182,1682,2339,2263,6257,6296,4562,5845,9848,2311,2058,4327,5368,7514,9484,9586,8175,3304,8223,5198,9196,6259,6530,3587,5619,1900,2706,2044,8500,8990,1778,7939,6316,494,2804,5621,5758,5633,3931,9428,2342,3269,9097,3867,326,8388,2709,4851,3836,161,9167,8514,9597,7827,1411,8454,6895,6896,2939,3914,8868,7616,7144,5431,8473,1226,209,5008,6711,4299,1262,9461,1674,7212,9655,9547,6523,870,8912,3048,8650,9867,2453,2898,5006,7482,1510,2001,3755,1406,1733,7115,9509,4506,9548,7911,5274,5972,1128,856,3115,3953,1210,8702,9383,2121,6975,130,4209,3687,3156,4043,9376,6678,9578,165,6322,1246,6318,6260,1148,9572,884,1770,2307,2941,1956,3346,464,2241,3122,957,8240,2792,5365,5308,4153,2662,5672,6663,8233,5932,7671,2798,9541,865,753,6289,8341,8607,6310,542,3375,8972,4565,6569,7525,9261,8718,4179,9783,7679,3408,2318,4189,526,7948,347,6398,2817,7201,2585,5445,9948,6287,7415,6769,9649,37,1339,3544,2249,2008,8073,5447,5824,8335,693,6405,7405,9569,2037,91,1069,4289,1931,6100,9996,9146,7615,985,8387,1192,4024,4814,1880,8463,1834,9879,532,6108,9845,1103,2015,3172,8671,1032,7686,8992,790,4714,7087,6304,3091,25,5458,4618,2081,9972,8247,983,8287,9758,1360,1468,7014,4117,2450,4002,8343,6793,8180,424,6813,9409,2807,345,2164,3994,1879,43,703,181,3325,2108,6467,3747,748,5811,2673,8745,1456,8368,1025,2853,6466,1286,8354,5086,6237,7465,847,407,79,5155,4047,5396,8263,8661,1800,9127,4375,8195,3243,2605,6779,2491,7347,1021,2879,7330,7070,6721,460,918,110,1945,6225,5305,8818,8986,4062,263,5990,3754,7585,8506,9789,7559,8690,4900,1302,6760,3809,8622,8191,1983,1538,1590,1260,8740,2457,2465,2970,5233,3279,3652,428,6633,1522,3319,9716,9969,9380,9952,962,9233,4,5246,6821,3187,6884,5828,5948,11,4794,1566,340,4890,2207,3053,5,9099,2867,3334,9359,3913,2722,2172,2357,2385,8599,8682,6123,7497,7409,7226,9994,5196,4045,7338,5996,1288,8603,8643,1366,746,9365,8144,64,6791,7980,2906,8305,557,2127,5973,3240,1882,8759,3322,3829,648,4415,331,4855,3989,8647,9598,4252,3315,4465,433,9732,7051,1592,3964,8106,1071,6784,2447,8863,5739,6582,7017,2915,2387,6472,2293,1570,5794,783,6387,7265,8200,9684,7813,1157,584,8009,4867,5466,8497,8143,7287,2720,9841,6407,297,8277,1807,5949,6623,4760,4624,548,8266,74,2835,2719,9069,581,5662,59,9528,9557,1936,7103,2358,27,4951,3439,3883,1434,8480,9740,2036,7639,8317,7527,4765,5843,4810,2124,3117,2038,6962,2253,4330,8091,8452,5122,4475,1461,7037,3011,5470,9580,8799,7223,9869,4554,9103,8897,8214,5645,743,2386,4028,8739,45,1481,2509,8294,6489,2940,6061,8831,8969,7765,4942,9256,2243,8068,7177,7499,2162,2987,9407,2967,9588,823,8133,134,438,2824,6250,6404,1989,3619,5849,2878,7966,8182,4555,3207,4347,3447,1372,3999,8311,9990,549,3580,5070,1220,7831,7328,7340,3924,9856,9723,3344,6491,2680,7789,1734,1974,9542,6034,8173,9413,8720,2416,8939,7759,4385,6603,8441,2937,8513,2901,4863,1388,4180,9441,2098,4732,6246,6042,4662,7311,5819,2951,8719,115,67,2046,9122,2764,728,4997,1871,2660,8418,7678,1450,8947,3093,942,580,1942,3763,1312,7230,2013,8429,4367,6149,346,9751,2679,1966,4561,9499,7855,4404,9942,2291,5815,4799,5491,754,2444,5773,689,9981,6622,4205,8246,3802,104,2440,6814,1494,2569,3760,2007,534,5983,8816,4967,2354,2671,2160,9646,4297,1855,3263,5067,3313,6090,24,7619,9741,6863,8563,1471,249,8060,2674,5436,798,5988,8344,7092,2398,3720,8602,7736,467,5582,4584,6665,8434,4096,9978,924,7013,9720,1634,7077,6388,8286,5363,2895,2743,7493,3712,1431,7708,7877,649,2815,4793,6419,6933,9544,1684,9575,5783,5324,9808,4681,7869,7268,8562,3278,6501,465,7578,2136,5795,4379,5608,1978,8018,8155,6819,5900,9679,4409,6849,8914,9396,2487,2579,1694,4004,7553,6636,5419,4927,6632,9692,5028,3233,9759,5958,1275,2618,3386,1000,5585,5112,4202,9126,9502,6148,8025,2373,2866,4227,1108,7749,7699,3547,1313,4963,5406,5808,3561,3061,3214,9896,2099,4711,963,9697,4700,3910,1019,9361,2234,1497,4442,2111,2257,3309,1875,9094,7538,4801,2850,9434,3997,125,3158,9124,2695,4499,8915,2401,5576,970,7134,6157,9087,3049,3354,6799,2670,9870,1836,804,7843,4665,9037,3504,5156,8403,6256,5961,8807,5327,9630,4548,6019,7922,6214,1142,4503,3420,7299,4572,8734,1478,8461,2209,4368,4052,5599,9381,9121,2382,8027,7315,5142,7568,2718,7969,2019,7335,4165,6575,8047,9503,5026,9953,4471,6743,7711,6112,1793,2004,4835,8597,522,6168,2317,5945,3947,8070,2494,1999,8475,2239,6810,7331,2156,5675,1480,3173,6160,7629,2565,2128,820,3851,1294,7996,7806,7240,8676,4682,4887,5459,1568,7515,7199,9863,3821,3024,8625,357,9944,579,1024,7026,9190,2175,1854,7816,7738,4996,7139,1251,2825,7841,5275,3080,5240,5425,9165,9986,6229,8724,1822,5830,3518,9438,2984,5593,8413,7857,8830,4160,5460,5202,2105,105,9315,3342,5895,6855,6130,3521,2518,386,8117,5188,1853,9882,6144,4417,6263,6422,1050,2755,599,426,2154,224,9526,4621,3817,3624,2693,9415,992,4693,6473,1627,5295,4992,1003,1179,2696,3277,5250,8272,2590,1678,5610,6620,8235,9219,7978,822,9355,8837,8794,2389,5786,248,6950,6315,2117,299,1412,2233,1427,3379,2586,5453,3205,5318,126,5955,7314,7269,3808,5109,4050,6657,835,5005,8265,3356,1790,3000,5939,9965,4504,1447,9151,3227,8738,6544,5753,4709,9163,3008,8131,8769,9348,3979,3515,439,7075,7968,3437,5359,5022,6520,5334,7291,6957,8206,2334,642,434,7485,2776,5201,190,2026,7094,2029,5727,5776,8700,8478,6759,6439,381,6920,6843,9956,9599,4267,3792,2742,1787,6875,2561,6963,1779,4779,655,4952,7132,4370,6340,3367,671,4747,8577,2142,9353,3359,2442,8447,463,995,7427,5369,1309,7434,5724,5038,2474,5020,8040,8014,9698,2851,9210,2756,6369,3428,1184,7506,5542,4075,9033,1632,8542,3417,5389,8552,4407,32,4444,4397,176,7488,1982,2143,510,6804,7828,3571,948,7881,8276,575,9293,1971,3830,8304,9007,818,1717,8764,5493,6661,9901,5090,6841,1261,4255,4111,9053,5935,692,6255,261,1781,1085,8016,9823,7152,5244,7001,7138,6833,7883,9834,1092,3361,4782,9799,9241,8791,1287,5283,3145,3152,3975,684,7998,455,4498,2320,5004,5791,3694,8736,4033,2328,8658,8841,4155,2783,3940,2277,1318,1325,4889,3470,8001,5730,9865,8008,4749,9049,7368,6000,5991,5391,4265,257,6959,9930,5362,52,8820,3295,7356,7761,1457,8886,2276,6314,1525,4831,1100,7088,9633,6495,495,2882,1499,1718,9862,8849,2519,5979,1594,7902,9297,2508,8746,4273,5361,8693,4402,7973,3039,9658,7306,9661,3427,4058,8662,6385,3349,4612,2093,417,4469,3870,7185,1909,2214,4617,5442,722,7547,5410,3528,4073,4432,1239,6125,3076,3745,2891,9474,227,5522,8524,4489,1939,3524,641,1182,9105,7681,1648,1336,8642,2144,5312,6829,5273,2734,1930,4774,3982,213,5992,8128,5423,4005,1866,1950,3972,9826,8006,5594,4208,4113,8519,266,9486,4903,9321,1186,971,16,8163,9324,989,8583,7174,9665,827,3607,5078,3411,7278,4339,3600,8488,5643,8709,3005,9520,1435,60,7646,1943,2572,9363,4399,5017,7783,7494,9440,6493,2547,6820,839,3615,1479,397,2351,6071,2991,3257,302,6203,1483,5928,3012,3519,4291,8850,7627,15,1783,3474,7236,9248,2085,6973,5414,3471,8227,5520,6359,6223,2131,4484,6708,8123,5129,6518,3403,8495,9453,1385,4261,840,3818,9874,5317,9341,2884,6375,809,5661,3909,7690,7432,1600,5855,5716,1844,169,7441,2717,4620,9206,3160,2050,3935,7175,7055,8639,5012,4815,2681,3788,960,3695,6634,5646,1299,7147,6024,5689,9179,310,6295,9356,6674,9674,499,8811,7819,131,4362,9323,9568,389,2083,712,9671,2503,50,3782,5377,6492,162,1944,3102,803,6463,2349,1771,6069,8221,7217,9242,6312,7393,5376,2061,9433,5355,5590,2025,1910,1815,4020,8369,9757,1608,6597,1937,274,5879,8313,1755,2557,7411,9224,2523,6838,3727,2139,8080,735,9271,7566,3647,1820,6209,7524,7767,2396,3569,8951,98,9063,5046,6638,8614,6960,1796,6477,4780,183,1282,1767,5259,667,2841,8899,8712,1345,66,5702,3678,1495,1521,9352,9543,7176,9310,2808,7878,242,2223,5340,9318,1023,7438,951,5110,2852,2563,1731,2981,1162,6114,4166,339,5839,1346,8696,6438,1013,4986,6659,1152,986,1775,1615,3642,5963,2216,8634,3806,8578,8683,217,4668,2794,281,2118,732,5035,2948,1527,3955,1619,6541,8802,8212,9624,9858,92,6583,7700,2813,260,173,387,4808,7470,8345,7715,3337,5906,7285,7403,5104,2603,6905,7868,4882,4980,2181,7046,2632,7213,8732,4223,9159,5467,9583,1979,5054,8225,5541,5161,9357,5530,6529,6969,3161,7651,1741,427,4439,1808,8443,7439,3996,2676,7396,3235,3007,7168,5514,6115,723,5474,6306,8102,5785,6726,1135,9993,5074,4745,5780,9690,4191,8405,3529,2103,3585,854,1028,1753,5528,3098,6366,2433,4651,6563,4578,3942,9249,3066,4823,2262,6702,8533,8754,4852,6447,3451,9815,3274,2636,9039,5471,528,1274,8130,5333,9236,8677,9516,9852,9772,3029,6601,4791,8558,4197,3875,4886,1238,8774,6594,1026,6653,3898,8063,6284,5021,2134,8618,1419,7633,1115,9275,8713,5478,1502,4915,3961,5703,563,4654,7915,8162,5219,9257,520,1289,31,7096,1516,8548,5666,1579,9240,7648,355,8609,9973,4595,5234,2890,5441,4820,8485,6299,4978,7416,2731,8096,8136,5174,3880,8391,4797,2992,2368,7928,9442,5910,1992,4911,3071,9119,2242,9178,7374,4215,9844,6468,5699,2314,2049,1156,6274,5439,9027,8835,9131,8761,6717,8158,5448,6943,5487,9471,1785,6172,5677,6608,8386,4845,9641,9800,4088,1940,5913,6329,2232,2966,4472,7730,5125,570,8150,2467,6423,2861,3343,4556,6300,311,3594,3638,3434,278,277,7125,535,4683,2745,9334,6817,8765,2685,7517,8256,172,342,8261,4516,13,8316,5483,3734,4199,4505,5690,5774,3527,2694,2699,6733,8834,1604,7122,6788,6222,3739,1654,8154,9688,9100,8884,40,7938,550,5989,7632,5430,1968,3766,3448,5152,76,4569,3660,7906,5277,7124,8872,946,6940,4534,5249,7603,2711,1811,9626,5032,6683,7740,1392,116,8459,5579,8172,9908,8856,9015,9829,3385,2370,5421,6614,4074,1994,1508,5223,2504,7242,5116,4755,789,3458,2076,4092,4212,270,451,9269,5231,8299,1443,3333,5338,7161,4126,3610,8065,2408,7325,552,6874,9636,2690,8958,4277,8171,225,5578,713,8845,4298,322,1076,8789,7688,7634,3540,1884,2822,8231,6298,1552,4099,4648,9423,7975,9371,8753,8848,4948,7653,4121,6484,5673,8113,5069,2691,1896,1254,670,2427,9247,7862,5455,2544,3321,3256,5624,4313,3868,937,6670,7739,2377,1629,4304,706,6082,1573,2220,4011,2430,238,2113,9871,2452,241,2510,9672,4807,6386,5350,2284,5553,9913,4854,4964,9955,351,3888,7539,152,9883,9465,8064,3974,3394,597,2205,5997,432,7336,1685,3013,1040,5415,4470,6272,8948,9518,3753,5310,9893,4408,4916,3865,2821,4862,9111,7734,5884,3689,372,5386,2173,8109,7380,4802,4511,4207,4306,7446,5488,4744,1068,5207,7951,4968,6682,4175,9997,7466,296,2512,4057,2621,4716,6267,6507,7471,9623,5632,7108,1661,4064,2556,9817,7840,3665,2065,7892,5617,9422,979,9009,3669,158,9322,8248,5802,816,6684,485,8529,1112,2881,2493,7680,8081,5912,5300,8940,1330,474,2204,7021,2536,4972,124,7362,9497,5837,5745,9164,8965,4026,7072,6435,9326,6648,9130,1245,9120,2335,3190,8968,3401,2210,2289,5733,7067,6958,6935,8984,8057,8616,7842,5693,9775,9344,8328,5102,6469,9753,5136,4393,4597,6795,524,931,1705,2928,9250,7725,7033,5812,194,8492,3636,7193,1907,120,2380,3144,6266,1774,6175,7808,8800,468,5752,8264,2790,3622,2999,3376,525,7583,4157,1476,2791,6479,5754,2814,6921,2490,140,96,6642,8545,3177,4256,9982,5177,4222,7304,3241,4846,8823,9045,3495,2802,9092,7642,4479,5149,1639,3009,1662,8575,5290,7060,3729,3699,5918,7074,8606,2839,7172,4383,7687,8970,4322,1846,106,2568,101,5569,504,3576,6416,7375,376,5424,3956,2059,8449,7261,3393,7833,5790,3543,9286,2177,4176,3666,5801,6514,3023,1650,5655,147,3850,3796,2055,9337,8797,6060,6906,2056,505,2983,4018,1697,1530,244,8840,3825,7790,3743,8528,3700,8966,7010,4674,5049,4763,7500,1961,3503,1894,5887,7225,3438,7622,7707,8737,8346,905,2976,1933,8352,8710,1,1439,4430,8751,6333,7495,6201,6400,4710,4735,6982,6433,3577,878,8435,5950,9949,8580,1231,801,3736,9654,3088,5494,3072,2560,8803,5533,7805,4463,7149,6233,6599,4009,3169,4579,6158,773,4669,895,9639,3250,2217,4551,507,9139,8362,4206,1993,8767,7751,5901,9420,3884,3784,4891,8410,7085,6020,9328,4101,5951,8196,5214,6243,8721,7882,481,9264,95,8804,3237,6014,1054,4108,2576,7692,2763,2069,2423,7644,2221,2178,5227,1777,6163,3085,8258,9750,7927,271,214,1163,930,7645,1647,3414,3985,5502,6341,1394,7442,2780,7956,7461,7897,330,5343,1902,8653,17,8323,874,9855,5536,3157,9681,5894,9287,3047,5993,2183,2167,5183,6995,163,4296,7030,4906,8851,5709,6159,3345,1609,9752,8438,2090,1206,2146,3424,1498,4788,1465,5225,6308,2818,9047,5457,3723,4581,4349,8024,6732,2723,3347,1870,9403,2686,9877,1597,5603,6602,4706,5211,3568,3082,1230,9726,7936,1867,4388,3153,3664,7829,8550,9295,7994,7704,7190,267,6630,1883,1698,5809,9625,2406,9012,2950,5668,6618,933,674,9226,3686,9452,7492,9421,6151,1007,3191,2244,5597,9342,1351,4486,5371,4201,2803,4487,5309,7510,1104,3560,8695,327,4300,8819,8651,1762,1144,5971,3843,7449,1066,4533,2553,6170,9,5534,4514,2014,4257,3232,188,8186,8268,2344,153,2773,7674,1399,1832,4162,8066,3572,6005,4962,866,892,5581,2428,4449,3384,9763,8641,1916,4924,640,729,5652,9192,7837,9456,4848,7697,3574,6758,4171,7490,7758,2198,4081,1418,8941,777,5750,745,3336,197,3564,613,8489,7601,5922,7664,2326,1577,4926,8725,6450,6228,5040,9618,5529,8621,5412,5722,1664,6891,6199,1906,437,300,6002,4400,3696,4821,7162,155,2047,9485,9154,867,6471,2101,7373,2942,7957,8973,5707,9189,5170,4021,720,514,919,3018,5518,7316,3589,7520,9890,9273,9096,8491,127,4337,3523,8290,1390,1247,1436,3275,5314,663,6154,3419,4105,1237,2393,6458,4633,48,4141,7898,7002,9964,1432,4999,2161,444,8613,9419,3452,2463,5609,3369,9822,2391,8793,7430,7850,6617,673,571,141,7005,4046,5933,4526,616,2753,5407,7799,5226,8523,6305,4102,9937,1042,9831,638,2063,9787,7270,6766,6418,9638,6427,6285,9645,5047,4443,8711,7513,1534,8743,1243,2526,5740,8670,6989,6516,6265,6142,3194,7713,7728,1167,9020,687,555,7937,9579,1908,9958,5354,7625,5544,6893,9280,396,2039,1334,6649,4596,5476,6195,5863,8828,9362,1368,7762,6947,2485,2150,6539,71,46,3126,9708,6964,9924,6001,3937,1912,5734,2741,6213,7251,9412,7903,4036,676,5823,4930,3987,5057,2580,2614,4254,9161,8921,3182,9431,2135,7376,3741,5075,2514,9106,8704,4874,9668,539,1582,8450,377,4264,9071,8371,4394,9443,1518,3077,5117,7112,565,4091,5558,7332,4100,5715,1665,6022,7049,5537,4071,1812,1190,3378,2945,6873,4015,2972,7160,7111,5042,5489,7018,2657,7197,4764,8685,4127,4345,8928,8931,1321,2916,9707,5708,6424,8498,7192,4939,6380,4396,2151,7241,9691,401,3981,3486,461,9694,4496,3614,2961,5623,6038,956,7157,219,9670,5936,3440,8623,2520,7920,1641,2258,8089,583,8895,6231,3993,7462,7502,5874,8515,3810,8814,9147,9308,610,1585,9186,9849,6010,1512,1252,2082,5885,9589,9910,3965,4170,6140,6543,3134,8747,7123,3733,5435,4082,1520,5782,3813,9992,7227,4752,5372,6194,3626,362,6476,7187,8808,6765,3405,619,8549,8925,2367,1203,3878,5880,7944,6339,1183,2893,9128,6890,3674,3364,9157,1015,7208,7541,7410,4708,5400,8213,1843,8813,2623,819,2708,7554,5031,543,8546,6897,6241,9482,2225,6164,5081,6880,9522,5055,3150,4965,553,7252,6586,3286,5658,9768,3362,5326,3834,2011,3675,7797,304,6089,3357,3656,117,5124,1652,3511,669,4880,9432,7050,6080,5068,5165,8624,5965,8199,4390,5209,6584,23,8054,5059,1202,1976,7487,3952,6211,2654,7312,7647,4684,3719,3175,7006,9046,2193,7128,925,2306,5237,7987,2880,2606,3731,7214,1448,9454,4174,445,2812,2968,8862,6128,9685,3946,9470,1207,893,2080,5714,7526,3537,7414,9766,5003,3465,9651,9222,350,9872,4934,8644,1656,1514,7989,3350,8112,2665,4509,3052,2920,882,7216,9748,8859,7279,9390,6939,886,3461,5178,8942,4232,2571,7498,4811,5072,8672,1134,3396,766,6286,8723,9221,1688,2355,2403,9894,1814,7400,1027,369,5208,792,2324,4640,7861,3464,5426,9728,6948,9999,8527,1267,5871,8399,2333,8957,2911,415,554,844,2754,2827,2054,7015,3432,6167,724,1618,4676,5732,5660,3602,8551,7305,2412,7723,1644,1616,6136,5103,7556,9546,5060,4729,2781,8482,6442,7854,1396,975,9743,4063,9909,2323,6877,477,6075,7614,6688,9155,3163,3374,7519,1692,7522,8465,8279,6,7613,523,4023,2281,251,1754,3040,5589,2653,1646,480,4553,9619,3838,5636,9613,3514,5803,7610,2702,2251,1864,3588,7076,9717,7194,6206,635,3657,1377,2980,5258,8553,7856,6012,8152,2264,5653,7655,3285,2912,4292,8011,9469,3751,6720,2313,2921,200,6323,4946,8608,2051,4006,4786,8487,4405,1242,9637,87,6965,2364,7343,305,5886,7171,6749,980,1046,1980,2315,1751,794,7116,5924,8584,2224,4543,1343,5499,4238,2672,6941,3640,4294,2840,3874,3371,5917,3222,8512,5747,1460,6714,6456,7195,9715,8673,2925,5477,6326,8423,3538,4697,6538,3341,4606,4619,1726,900,8395,1347,5964,518,6268,3604,9368,7063,8187,6595,8994,4138,8879,9414,4742,1255,5833,3630,4398,4914,8375,5505,3300,5065,1750,7489,6631,9001,1161,1285,9058,5134,4302,4426,2715,9360,2849,6155,8854,8331,3425,4822,8706,5265,1350,6934,7543,2642,3746,6113,6218,1828,3639,5341,4328,6499,8072,682,733,9427,9463,1349,5562,2779,6103,4279,6436,5793,3774,99,4995,620,3849,7836,1367,2870,3623,9866,1475,4508,5549,3164,2871,3079,2848,4055,4692,8945,2331,5076,6126,8655,6528,3663,5847,6475,2828,1889,1819,6615,367,7768,2304,4258,6454,2468,6212,6876,3907,2801,1554,699,7557,9527,6084,6049,5452,3824,1949,3059,1080,2729,860,5962,3460,7722,8002,6063,5270,4234,4593,7345,973,9424,7020,7717,9300,1913,9085,4570,3081,5437,8953,2847,6131,3752,1935,7346,1655,8110,7673,8197,9687,6588,1756,2350,7777,6465,8084,8871,7579,4876,6271,6768,1571,861,7248,7990,6785,2149,6811,953,8226,8042,4792,2405,4272,3567,7683,1946,3368,2549,2907,4133,4720,1284,5325,527,7130,9537,9367,6900,2472,3887,8169,6755,2589,7275,2521,7802,5162,7889,588,1018,8901,8781,4086,7244,1384,2347,5554,2388,5179,8810,9521,487,8122,9780,6350,9340,4589,3929,1194,3119,5418,2716,547,9749,6099,9395,8069,9664,4941,3211,9900,7024,6297,5195,2235,7870,6972,1888,7062,2965,2698,4702,9193,1841,3252,6610,4303,4611,5449,9416,9019,2003,4218,771,3,6660,1605,4410,4384,595,6831,5506,8557,6510,3381,6455,5691,9123,1307,608,3670,4485,5834,3389,4776,8087,3489,8302,6909,2092,2555,453,7621,8170,1327,8627,1268,57,5637,1569,7919,8099,1595,8705,2171,5853,9563,3353,9922,1453,5342,9784,4049,9074,5292,5893,4530,7371,9072,3827,6709,3213,1847,1045,6668,5641,591,9995,4655,6842,9349,8111,237,3526,1725,9513,8326,4583,4771,4480,344,3919,3658,1469,1898,3260,668,8539,8198,2684,5827,7597,3681,3308,4528,6104,6238,2500,4998,3391,1078,8521,4558,7053,3872,3185,3978,1837,2486,7150,5942,5820,360,6008,4680,9825,5768,7054,8541,3400,2152,8979,1782,5262,9289,7274,1181,7573,8617,5982,1337,8151,8785,9118,6868,9621,4733,3245,6041,3298,1689,2170,7663,1444,38,8935,5216,9399,8193,2259,9889,2455,230,1637,7772,65,5564,7266,3894,5332,6288,8760,9517,5620,4686,2641,2738,5041,4979,1886,1420,9960,8876,5539,1727,3499,8243,5159,5278,707,8139,7156,7726,6725,2448,8373,8292,6443,1622,6184,5297,897,8678,2429,7589,9402,1197,2147,2531,8283,6650,3797,4226,2533,306,8833,9138,734,5451,3314,2594,9041,9918,5929,9530,6628,9091,3281,2988,7143,1567,4975,3691,2903,2201,7210,7163,8896,6560,9333,7871,3595,3761,5301,3176,3109,2,7572,9435,9770,2122,7884,4885,5101,7246,630,3685,7417,1107,8936,3174,6587,9754,9864,5804,6552,5659,7918,8686,2296,8044,5048,3498,6462,6402,2728,312,7359,8517,1547,8742,6146,4457,1370,9843,8654,8361,7895,6498,9767,6325,1087,1022,1095,5203,6532,8377,2420,2022,1739,7453,9032,6360,6017,9115,1198,8561,6894,9773,1799,8568,3016,9218,9604,4704,7231,2057,3697,6336,6488,5374,8390,7003,1033,9089,9068,7947,5160,9320,9109,3270,7263,1073,7344,4844,2482,7401,2540,9003,7479,4003,6999,8097,7262,374,6064,4311,977,2956,8095,2449,7705,9481,5797,4056,3208,9329,3506,8955,5205,1887,4525,8708,6848,7272,2506,8950,7661,2960,4172,1196,3212,6627,3355,84,9410,1723,9669,7382,3296,384,6865,8976,406,2507,6506,6976,7921,5222,2434,5428,6555,1699,2683,1088,1925,1960,2733,5416,1572,5905,4944,965,2534,2611,5148,9842,2260,3988,5420,7773,2566,3454,9567,8153,2073,3871,6676,9811,8890,5328,969,7785,4727,3790,5158,3976,9680,2799,5130,7100,9634,4949,3714,683,4210,429,8501,6494,3087,3189,9370,2100,4249,293,9429,7032,7450,6992,6073,9400,2189,5701,3951,7218,7326,1952,5098,850,4280,3520,7817,9519,3715,9064,1244,6330,4933,5111,9673,3517,8878,8274,6773,7959,1693,4178,7496,6446,5316,328,2924,1986,6362,9628,932,4993,2495,7731,2028,6740,4134,5345,5596,9595,1903,1233,7090,5872,763,6672,6951,4305,3147,2230,3629,9925,9388,6258,9769,1292,7814,9209,2796,541,8444,6432,3866,185,1529,470,8857,1679,9656,3228,4243,2266,8997,8076,6624,8755,4987,6092,5516,3977,7657,7743,9596,2096,3042,4761,1449,5615,2229,7580,5322,5920,6187,7754,6500,8055,4902,7164,5394,3596,7290,6542,7395,9582,2053,1666,4090,4875,5061,2197,4634,7133,7413,6192,8779,6196,2829,4743,2797,2551,681,1464,9080,5878,58,2934,2640,5970,7350,3583,3247,4982,8291,4456,2806,6853,1146,4642,5650,5050,8898,8020,8259,1643,240,471,7867,8630,923,8780,4535,9055,9653,4575,7864,5697,2750,917,3606,3086,7960,5172,5664,1410,2843,9458,343,1776,6102,9347,2687,9785,2470,4308,5700,216,2163,419,1798,5926,4594,3218,3468,9515,4156,7339,9200,6998,9404,1795,5517,239,336,1724,7166,7724,938,5561,4660,7086,5181,3879,3030,1850,887,7093,8183,7669,5299,5968,8891,5789,929,295,2383,4248,8457,885,3195,2226,2300,6750,2321,2297,2481,3950,1542,6191,3661,7567,1995,7916,3390,3505,4813,4391,8280,9571,6202,9265,5512,2598,86,4089,7188,1329,5772,5257,1277,8586,6675,4935,1426,9916,9581,146,3171,2247,7294,4076,282,1918,1417,2048,7110,9405,4881,2425,9272,6027,3001,7040,8920,435,1093,9439,4567,462,3382,3327,1386,4635,333,788,4966,7907,8815,7551,3339,3616,3958,4245,6580,7203,5721,5685,4001,8041,6023,400,3777,3159,2068,1969,3019,4904,8296,6918,3073,7381,5723,1053,2633,5565,3041,7764,8554,3757,4123,8307,5907,313,8963,379,5908,2527,2775,6278,6503,7196,5019,7847,741,9215,7872,1117,9173,7404,8892,3497,8956,5331,9166,6548,6478,5706,7140,3912,9306,8900,6790,7983,81,21,4119,3209,8431,601,6057,6731,3549,8874,6118,4605,2947,7472,8167,8397,2187,1845,1011,53,8049,6412,2043,8120,9136,4333,4494,9585,9738,6988,8165,8059,4638,9052,4491,308,9957,8824,7804,8659,7976,4403,8959,3562,8466,4130,852,5347,4029,9733,6719,6881,44,7811,7706,8455,307,9313,2153,7509,2788,63,8067,8477,8559,3886,5349,4694,7834,5616,7099,4355,3276,3038,414,9473,6869,1258,7025,1293,9584,2771,8749,795,853,8271,2227,6955,4940,8646,7474,7477,5705,2363,567,9946,3070,6220,9364,7698,3488,5545,1395,9239,6317,4746,6885,6593,482,5832,2130,9846,2016,5818,6744,1749,8178,846,1462,408,4901,3858,9686,3957,9511,7548,5284,8127,5073,9731,6345,398,1710,9779,5857,4538,220,9559,9317,4357,8716,4068,4956,8184,8590,1324,5930,3780,3198,9338,3244,114,6845,7974,8359,530,8652,7981,3980,3370,7961,2456,7769,9771,8906,450,7607,4734,7521,5966,4341,3481,2900,5548,629,9643,1433,4321,915,6524,7379,6882,6609,9168,1621,218,493,4985,4947,3917,2341,8284,1442,5206,2231,5147,7779,6517,483,7631,3525,204,3881,358,2944,4958,4203,5461,4990,402,193,1143,7523,5256,6003,5083,5264,688,6879,2126,7640,6856,1614,275,5856,8729,6221,73,375,4626,863,5998,423,7478,1691,6908,3267,2607,8338,8826,1630,1803,999,4310,750,9985,7941,5573,1758,7322,1701,5454,4350,2245,9574,128,9814,3789,8926,7638,751,4351,901,7170,4685,3326,944,3599,1970,1199,6952,7611,8086,4190,4860,325,7117,1653,4585,4464,6169,1736,4196,4677,3895,5475,2689,1086,4163,9648,4450,9278,3708,3556,5831,1638,4613,1528,5846,9245,7436,2088,279,9177,2908,4381,7361,2168,7298,3795,7562,2909,7563,276,5947,160,5552,5521,167,3110,7224,8330,9853,8100,2758,7503,2027,7179,6574,3805,5320,6913,8032,198,1932,9477,1849,8402,5344,6081,9384,5106,4173,5097,2299,1987,8788,4897,9812,5743,8255,8114,6864,8238,2697,8924,8239,7818,1463,1127,9806,5875,7141,9191,4276,7105,7746,573,3475,215,3563,8504,1624,9373,5888,9408,9647,1259,791,320,8974,9282,8474,7419,6585,949,7863,2435,8748,7620,1984,6616,824,3261,5656,368,4696,7695,9418,5030,3667,430,7899,4492,9401,5352,3553,90,8257,912,5095,8416,2949,6859,6753,8798,8436,8236,5915,7391,4338,8035,6321,4790,6783,1633,1539,9188,1797,8934,8476,7935,664,760,7129,348,286,5383,2935,1707,9480,5366,9614,7264,9468,9809,2079,6667,22,7940,2811,7232,600,5169,6174,5523,4455,6094,5825,5138,8817,5622,8993,721,2892,8192,1008,4568,6047,4536,1766,1988,1545,7592,4645,653,5357,4314,5598,3814,1831,4644,1240,4229,3487,4187,177,3915,533,1667,7925,1298,9929,6076,6987,7064,5814,9739,4515,1383,8697,3791,769,2932,484,1764,3050,9710,2273,5189,9298,1114,6738,1752,8300,2397,7913,6846,4431,7386,3855,1317,1306,6058,7392,8657,1972,6800,7249,2583,3598,1951,7135,9327,7929,5217,8784,4905,35,7009,9705,6331,2721,6641,2002,1253,2024,4007,3627,1304,9881,3934,184,6171,5339,5380,7048,6120,2546,9782,4884,7181,142,7348,9714,8215,7095,8210,9816,9379,6816,3280,9632,2624,9148,2800,4818,660,8181,6809,2418,4544,1132,711,7600,2666,1493,4717,680,1712,6378,5392,6712,6850,1794,3948,1876,4766,9354,1166,4132,5446,4224,4159,3612,502,1677,8778,9979,9279,6741,2730,2864,9227,5236,5757,6085,4873,9828,3831,3229,5044,2359,8357,4955,2658,5720,6673,1598,6786,9309,457,8249,6929,3877,9397,1523,7618,5891,9535,4268,6699,8758,8692,5682,6364,2329,6426,4539,4603,9608,61,8518,3832,1090,7992,7649,7352,3634,2832,6772,9514,6417,6138,3239,8861,585,1172,1423,3507,174,315,5492,1720,1264,947,4839,1934,5010,7820,8980,8209,1319,4376,5128,3137,2119,1403,6393,7267,3860,8701,1873,5422,1043,6681,8411,6032,3659,6377,5001,4200,7798,636,1806,3998,776,4372,747,8366,4290,9017,9700,8493,7480,1593,9202,5560,6367,8762,3444,4087,4576,3162,6852,1715,5674,6280,3889,7575,7658,1606,6248,5868,2473,9553,4070,5027,3266,1072,9444,8771,9231,5595,2530,8694,2564,8103,5600,9487,8363,7283,1683,9277,6173,7061,8137,1438,7776,5242,665,4387,2943,2238,6872,2655,42,7341,6368,1891,2550,7369,7394,1035,9187,3149,2592,5243,945,2542,1562,7237,5607,2157,7838,7011,4198,3412,9134,9162,7893,8855,108,1537,5228,7565,6932,1102,4251,4703,9449,6088,966,3922,9498,7984,8159,2664,303,5137,5276,7307,6365,7089,1660,144,9701,8636,8773,3557,4239,1920,647,4531,9805,26,7617,9283,3510,7198,2919,6613,6420,7243,1221,8004,1147,2770,5798,3180,9090,6991,9721,1482,7215,228,4832,659,6079,1911,9836,8938,9005,9389,3859,2918,2969,1788,4244,6448,9144,5175,2751,7121,4850,2084,4022,2973,4288,7222,4154,5184,3992,245,6421,7475,6970,678,8532,6052,4672,2710,838,5731,4440,6984,1031,4281,2677,4395,1413,9631,3203,69,6533,4164,3193,8846,5759,1899,3002,3143,8442,2823,2639,9983,425,3215,2651,902,3679,7795,833,3509,9914,6645,9021,7574,3409,5612,7045,2933,1489,7081,4748,5469,9827,5563,7549,8147,6072,1034,9230,5120,545,7066,7796,2476,5851,2437,3552,6907,7896,7421,7879,6397,6379,1295,1322,3991,9095,7542,1415,1722,9448,3605,5771,880,7059,4510,6459,3476,1131,9912,4278,4928,4459,2369,6696,2319,6232,1359,9301,7733,6710,3820,498,8098,6763,1010,8509,5679,4103,3939,335,3815,2165,6862,8960,9425,1869,6568,813,8315,9377,5401,4286,9076,9765,5096,7666,8260,1792,9742,5952,1201,8911,288,4282,9971,8201,8982,666,4476,5080,9887,5409,3094,8398,2996,8660,1574,3035,8278,4571,1280,2332,6689,9183,1256,4858,7429,4326,2905,3106,7113,7550,3772,4770,1400,1062,145,6190,8177,8565,178,9059,6936,4270,6666,5769,4837,9791,7912,1387,269,5911,2133,1926,3429,5931,5062,829,1358,2196,2842,7154,4369,536,8082,6781,3303,129,3709,780,4623,5113,4659,8543,6045,859,1923,6033,6346,4411,7183,3692,5749,8245,1270,5838,7355,9662,7766,2443,9551,558,3558,8917,7650,5850,6938,628,9857,4824,7424,8421,997,2910,2831,3655,3272,6748,1543,5686,6373,394,2627,4725,2650,2971,5016,8944,6946,154,4316,7533,7945,7737,1271,5066,7390,634,5063,738,8544,9350,4366,3732,582,6746,7098,8105,888,9229,9795,5941,6277,4048,4758,4637,1037,740,1215,1474,5323,9554,83,6018,2477,1551,7628,479,5388,574,1452,9963,2647,5881,5093,1948,7295,3654,2597,4741,3591,982,2248,6403,4080,8714,8522,4059,6854,4093,6824,6899,6902,7383,6707,1055,5572,4893,3637,4324,2488,5127,8867,7624,4413,7505,7271,2360,762,800,2399,3192,1746,8033,7693,4601,6303,2567,9008,5417,7696,447,926,6866,1690,5167,6570,208,268,5719,2787,1342,843,6309,4552,6515,5000,940,6567,8795,9534,8916,8045,9014,7846,112,1625,1064,7109,8610,972,2158,8601,4019,2283,301,2659,578,3704,705,1425,3310,5114,5602,1291,2859,5762,4826,2308,2381,2759,2279,3443,1868,3017,5413,4167,1857,5862,6598,2265,7422,8093,1119,7250,5353,4495,9835,998,8913,8384,5994,9915,2023,2145,353,5411,7665,1455,7934,1136,103,4478,3121,5296,9398,9075,5999,622,4084,9102,8211,9385,612,3402,2637,3787,4970,5099,9868,9459,2609,2990,6827,7372,2010,264,4136,9861,2271,9113,8560,1149,1613,4777,1126,1556,8927,4301,2298,4106,4344,8308,5253,752,7292,4436,2268,9603,3057,894,5640,6430,3932,352,2986,8929,3183,56,3959,7281,3231,8479,8472,3107,9211,5100,5629,4031,285,2713,8635,5403,8776,3291,8615,3863,4039,1257,2575,9088,5725,1310,2097,7905,6549,9903,2727,6797,8166,8325,3196,5946,7964,836,1735,7656,8852,4146,9931,1440,9711,4312,3492,9436,151,5039,1696,7324,5687,6097,289,519,9462,6802,8430,5817,139,6578,1501,6777,1631,5604,6107,5463,7801,7148,3410,6778,8999,7967,9899,4775,1320,6990,9034,6230,5712,1915,2857,3104,9611,3945,1188,5696,1738,2267,2040,85,9561,8975,8023,7058,6078,2489,6508,5281,5718,5995,4913,6652,4984,4909,6320,1374,7097,2075,7714,2392,8538,9677,378,5953,9906,7540,8894,7952,6502,9746,691,9195,9818,4736,4145,509,3897,6581,9238,93,5384,6166,9898,1176,9512,5151,5498,2869,8000,3816,6253,9255,9042,1365,6392,168,8408,6348,201,2137,2497,9904,3395,7354,7486,5764,392,8312,1458,6015,3063,3197,1742,3154,4329,1401,2682,9907,2067,4615,6139,4817,990,7297,132,6414,5144,5684,6039,6262,7106,9006,808,7577,3688,3949,1601,6324,8757,5480,6527,7546,1005,3494,4707,6867,5902,7908,2316,9304,6686,9683,8689,2464,6916,3329,1195,5173,9083,4228,9182,2777,5591,243,7667,2726,701,8881,4938,7245,4908,4564],[[6081,9384,5106,4173,5097,2299,1987,8788,4897,9812,5743,8255,8114,6864,8238,2697,8924,8239,7818,1463,1127,9806,5875,7141,9191,4276,7105,7746,573,3475,215,3563,8504,1624,9373,5888,9408,9647,1259,791,320,8974,9282,8474,7419,6585,949,7863,2435,8748,7620,1984,6616,824,3261,5656,368,4696,7695,9418,5030,3667,430,7899,4492,9401,5352,3553,90,8257,912,5095,8416,2949,6859,6753,8798,8436,8236,5915,7391,4338,8035,6321,4790,6783,1633,1539,9188,1797,8934,8476,7935,664,760,7129,348,286,5383,2935,1707,9480,5366,9614,7264,9468,9809,2079,6667,22,7940,2811,7232,600,5169,6174,5523,4455,6094,5825,5138,8817,5622,8993,721,2892,8192,1008,4568,6047,4536,1766,1988,1545,7592,4645,653,5357,4314,5598,3814,1831,4644,1240,4229,3487,4187,177,3915,533,1667,7925,1298,9929,6076,6987,7064,5814,9739,4515,1383,8697,3791,769,2932,484,1764,3050,9710,2273,5189,9298,1114,6738,1752,8300,2397,7913,6846,4431,7386,3855,1317,1306,6058,7392,8657,1972,6800,7249,2583,3598,1951,7135,9327,7929,5217,8784,4905,35,7009,9705,6331,2721,6641,2002,1253,2024,4007,3627,1304,9881,3934,184,6171,5339,5380,7048,6120,2546,9782,4884,7181,142,7348,9714,8215,7095,8210,9816,9379,6816,3280,9632,2624,9148,2800,4818,660,8181,6809,2418,4544,1132,711,7600,2666,1493,4717,680,1712,6378,5392,6712,6850,1794,3948,1876,4766,9354,1166,4132,5446,4224,4159,3612,502,1677,8778,9979,9279,6741,2730,2864,9227,5236,5757,6085,4873,9828,3831,3229,5044,2359,8357,4955,2658,5720,6673,1598,6786,9309,457,8249,6929,3877,9397,1523,7618,5891,9535,4268,6699,8758,8692,5682,6364,2329,6426,4539,4603,9608,61,8518,3832,1090,7992,7649,7352,3634,2832,6772,9514,6417,6138,3239,8861,585,1172,1423,3507,174,315,5492,1720,1264,947,4839,1934,5010,7820,8980,8209,1319,4376,5128,3137,2119,1403,6393,7267,3860,8701,1873,5422,1043,6681,8411,6032,3659,6377,5001,4200,7798,636,1806,3998,776,4372,747,8366,4290,9017,9700,8493,7480,1593,9202,5560,6367,8762,3444,4087,4576,3162,6852,1715,5674,6280,3889,7575,7658,1606,6248,5868,2473,9553,4070,5027,3266,1072,9444,8771,9231,5595,2530,8694,2564,8103,5600,9487,8363,7283,1683,9277,6173,7061,8137,1438,7776,5242,665,4387,2943,2238,6872,2655,42,7341,6368,1891,2550,7369,7394,1035,9187,3149,2592,5243,945,2542,1562,7237,5607,2157,7838,7011,4198,3412,9134,9162,7893,8855,108,1537,5228,7565,6932,1102,4251,4703,9449,6088,966,3922,9498,7984,8159,2664,303,5137,5276,7307,6365,7089,1660,144,9701,8636,8773,3557,4239,1920,647,4531,9805,26,7617,9283,3510,7198,2919,6613,6420,7243,1221,8004,1147,2770,5798,3180,9090,6991,9721,1482,7215,228,4832,659,6079,1911,9836,8938,9005,9389,3859,2918,2969,1788,4244,6448,9144,5175,2751,7121,4850,2084,4022,2973,4288,7222,4154,5184,3992,245,6421,7475,6970,678,8532,6052,4672,2710,838,5731,4440,6984,1031,4281,2677,4395,1413,9631,3203,69,6533,4164,3193,8846,5759,1899,3002,3143,8442,2823,2639,9983,425,3215,2651,902,3679,7795,833,3509,9914,6645,9021,7574,3409,5612,7045,2933,1489,7081,4748,5469,9827,5563,7549,8147,6072,1034,9230,5120,545,7066,7796,2476,5851,2437,3552,6907,7896,7421,7879,6397,6379,1295,1322,3991,9095,7542,1415,1722,9448,3605,5771,880,7059,4510,6459,3476,1131,9912,4278,4928,4459,2369,6696,2319,6232,1359,9301,7733,6710,3820,498,8098,6763,1010,8509,5679,4103,3939,335,3815,2165,6862,8960,9425,1869,6568,813,8315,9377,5401,4286,9076,9765,5096,7666,8260,1792,9742,5952,1201,8911,288,4282,9971,8201,8982,666,4476,5080,9887,5409,3094,8398,2996,8660,1574,3035,8278,4571,1280,2332,6689,9183,1256,4858,7429,4326,2905,3106,7113,7550,3772,4770,1400,1062,145,6190,8177,8565,178,9059,6936,4270,6666,5769,4837,9791,7912,1387,269,5911,2133,1926,3429,5931,5062,829,1358,2196,2842,7154,4369,536,8082,6781,3303,129,3709,780,4623,5113,4659,8543,6045,859,1923,6033,6346,4411,7183,3692,5749,8245,1270,5838,7355,9662,7766,2443,9551,558,3558,8917,7650,5850,6938,628,9857,4824,7424,8421,997,2910,2831,3655,3272,6748,1543,5686,6373,394,2627,4725,2650,2971,5016,8944,6946,154,4316,7533,7945,7737,1271,5066,7390,634,5063,738,8544,9350,4366,3732,582,6746,7098,8105,888,9229,9795,5941,6277,4048,4758,4637,1037,740,1215,1474,5323,9554,83,6018,2477,1551,7628,479,5388,574,1452,9963,2647,5881,5093,1948,7295,3654,2597,4741,3591,982,2248,6403,4080,8714,8522,4059,6854,4093,6824,6899,6902,7383,6707,1055,5572,4893,3637,4324,2488,5127,8867,7624,4413,7505,7271,2360,762,800,2399,3192,1746,8033,7693,4601,6303,2567,9008,5417,7696,447,926,6866,1690,5167,6570,208,268,5719,2787,1342,843,6309,4552,6515,5000,940,6567,8795,9534,8916,8045,9014,7846,112,1625,1064,7109,8610,972,2158,8601,4019,2283,301,2659,578,3704,705,1425,3310,5114,5602,1291,2859,5762,4826,2308,2381,2759,2279,3443,1868,3017,5413,4167,1857,5862,6598,2265,7422,8093,1119,7250,5353,4495,9835,998,8913,8384,5994,9915,2023,2145,353,5411,7665,1455,7934,1136,103,4478,3121,5296,9398,9075,5999,622,4084,9102,8211,9385,612,3402,2637,3787,4970,5099,9868,9459,2609,2990,6827,7372,2010,264,4136,9861,2271,9113,8560,1149,1613,4777,1126,1556,8927,4301,2298,4106,4344,8308,5253,752,7292,4436,2268,9603,3057,894,5640,6430,3932,352,2986,8929,3183,56,3959,7281,3231,8479,8472,3107,9211,5100,5629,4031,285,2713,8635,5403,8776,3291,8615,3863,4039,1257,2575,9088,5725,1310,2097,7905,6549,9903,2727,6797,8166,8325,3196,5946,7964,836,1735,7656,8852,4146,9931,1440,9711,4312,3492,9436,151,5039,1696,7324,5687,6097,289,519,9462,6802,8430,5817,139,6578,1501,6777,1631,5604,6107,5463,7801,7148,3410,6778,8999,7967,9899,4775,1320,6990,9034,6230,5712,1915,2857,3104,9611,3945,1188,5696,1738,2267,2040,85,9561,8975,8023,7058,6078,2489,6508,5281,5718,5995,4913,6652,4984,4909,6320,1374,7097,2075,7714,2392,8538,9677,378,5953,9906,7540,8894,7952,6502,9746,691,9195,9818,4736,4145,509,3897,6581,9238,93,5384,6166,9898,1176,9512,5151,5498,2869,8000,3816,6253,9255,9042,1365,6392,168,8408,6348,201,2137,2497,9904,3395,7354,7486,5764,392,8312,1458,6015,3063,3197,1742,3154,4329,1401,2682,9907,2067,4615,6139,4817,990,7297,132,6414,5144,5684,6039,6262,7106,9006,808,7577,3688,3949,1601,6324,8757,5480,6527,7546,1005,3494,4707,6867,5902,7908,2316,9304,6686,9683,8689,2464,6916,3329,1195,5173,9083,4228,9182,2777,5591,243,7667,2726,701,8881,4938,7245,4908,4564],[756,6966,700,3608,3142,4079,7612,5261,1373,3983,4149,8637,2071,7988,4204,2922,5866,5224,8085,9253,6680,3099,4547,4667,6016,3516,2409,3648,8176,7909,205,5531,9446,6815,7317,1074,4247,8205,6637,284,3166,8537,9566,817,1278,1743,9725,3799,8090,6844,3284,8382,8204,2897,9970,6794,3129,3554,9054,4365,3873,3453,6208,2091,7078,1668,1445,4540,6205,1791,431,2752,3477,7189,2438,8460,4181,9305,9644,2041,7782,441,4976,685,1082,159,2626,371,6077,2887,8839,365,9205,7313,9382,1081,4879,1922,1862,6718,941,7570,3812,5736,4241,993,4625,3649,1702,3609,5267,8587,4012,1279,2581,7703,1823,4713,5356,1355,7859,6812,6980,1314,9084,1669,5882,3306,8012,5892,2819,6945,3785,452,166,6381,8003,8052,1612,8115,9652,9532,9198,9386,8048,8288,7114,9666,602,9451,4137,3550,9025,9891,651,7057,4142,334,702,5381,2285,1441,3565,3579,6770,6621,4550,3366,7423,4482,1544,8842,1191,5229,4753,7186,8593,5937,9593,3905,5631,4895,9243,490,8270,1719,6828,4140,6625,6956,7608,2955,4767,7302,1964,716,9437,9536,8763,904,1397,5867,3021,695,7142,7126,9181,6654,6903,6496,8877,1703,6626,5269,3234,7886,6607,8446,4590,6687,4220,9967,4577,9290,4878,7358,6639,1036,2532,9475,3730,2667,5390,2963,3779,3399,2668,4754,7946,1924,1813,2838,7308,3037,3724,5082,2599,6996,4428,2274,1118,9776,2012,9029,8407,6198,5648,3705,988,9612,6116,6888,8207,8626,9984,6565,9170,7120,2009,5481,107,5976,8946,6083,6152,3926,6249,1861,9171,7741,7815,5813,1991,837,4827,6551,2634,3246,757,8179,8071,2789,9141,6701,9591,6226,3493,907,5967,877,9736,767,5164,1097,2845,1065,825,8075,7469,1809,742,675,2746,6857,2116,4110,3839,4828,9617,9065,4529,7721,569,7718,976,4657,2213,2785,4718,3165,6384,3423,1004,9911,8564,8904,1269,9657,5938,5398,337,1765,3632,1747,5450,2616,2669,5546,9483,5302,7052,5770,1044,1540,8730,6647,7750,9184,6511,5153,6025,9056,4691,7044,6723,8190,9824,10000,5462,8905,646,5525,3803,3027,8801,1225,3036,8393,2431,2615,9935,8228,8505,4246,3044,8989,6399,6261,2327,1981,1459,7943,9026,7635,3783,9719,7958,2192,9108,6121,2436,3798,256,1296,4994,7426,6106,247,4356,4517,1121,3822,7384,8301,8046,7259,3043,8309,2778,8253,9704,1671,3970,7334,8919,5385,3613,3711,5131,410,726,148,4675,1241,8691,4983,123,5397,3146,70,2735,2816,9043,9540,4371,212,4647,879,3065,1532,6806,5373,9044,5663,6985,7073,883,6981,4392,5877,6968,5916,9284,7036,7757,7418,9030,6559,5944,9491,501,1105,1761,9838,1740,1356,1681,3135,1640,2174,8668,697,2692,1526,7637,4527,537,5496,3320,2574,6513,3483,6592,7102,3773,9884,5495,8503,731,1623,2345,3861,592,3590,5289,4481,1548,9185,8417,770,5472,515,9729,6334,2522,8440,8364,8334,189,4819,4973,454,253,1897,1228,3046,7778,6901,9174,6048,3740,5009,9061,4679,8125,9676,3242,2169,7378,9938,2188,7483,3768,6805,3318,4152,8022,5303,1881,1506,871,1137,2461,7173,393,3127,508,3676,1039,3928,7260,6204,2714,7280,805,9934,6643,4065,8844,9060,3062,440,5139,7321,4458,7238,4253,405,6756,3927,868,4424,2475,815,2656,1729,6870,814,9560,8439,1957,3921,8019,8806,3762,5751,4870,3973,4283,9737,4798,7131,6700,586,9564,939,785,2834,8964,8203,7431,3467,3682,7993,6445,3581,9391,1038,9830,2384,1094,3869,8967,2372,4307,1234,6355,5678,196,5898,3251,4989,298,1591,855,8217,9476,7425,8875,273,2926,8822,8108,2712,2045,8792,7594,7253,6886,6619,319,4466,5402,6425,3288,1174,3804,7080,2109,3793,4353,3837,9505,1446,4537,5876,5395,5238,1830,8772,7780,8530,1768,6736,8535,954,2017,3392,1802,7406,7165,8887,7532,4069,3617,3885,2577,5784,9251,4193,9778,4147,2190,4809,2736,6395,3593,4559,6671,9332,5268,6481,1333,3794,2125,1531,3124,6486,1578,7233,1077,7007,3441,3645,1371,9479,8337,8051,5279,9892,9851,4868,5735,2414,1110,851,9220,4715,4542,3068,259,8374,4477,2896,3482,8526,5698,5671,456,8573,869,2176,2833,1020,5200,8039,246,7822,4360,2374,5252,8556,3548,2312,8809,5337,7397,1235,1998,3323,9609,9223,1187,6704,8327,5180,1511,5479,5587,2863,6313,5618,5497,1109,4135,7512,4849,3597,6531,6562,6165,9562,9067,9682,1185,5501,30,236,3388,551,5844,4437,6662,6954,4768,4382,5649,5681,7712,2087,388,9762,4864,5726,8985,4563,3906,3862,7582,8866,3854,383,7792,8010,5056,2883,7518,7995,9225,8088,1603,1113,4756,9810,506,1721,9790,2855,1407,2539,3462,3933,3181,4378,2768,4148,399,7576,9455,488,3075,6451,3118,7825,1607,8930,6742,3578,2964,2953,9876,6776,8502,5230,9050,3131,3990,280,4128,1557,3786,9104,7282,5024,6606,5427,9886,4513,9573,4522,2352,2740,4233,8156,4695,4343,3450,5023,1745,5486,9607,8585,8222,2872,8954,9507,739,2608,8419,5221,1002,4800,1211,1217,7752,4445,1402,5896,4010,5584,5940,4689,8229,7670,511,5507,9803,7888,9936,6837,3690,9028,5519,7353,2558,7875,2033,6923,2419,6098,3826,8620,5015,9917,8880,7083,7028,9689,9954,6480,6282,7971,3034,6110,3221,5741,3916,491,6065,7084,7127,5575,6457,672,1505,8077,4783,5864,2228,704,3200,7158,2439,186,8903,8962,661,5860,4435,6604,6703,9594,329,1599,1584,8516,7091,294,8812,696,4295,5683,7716,7473,7851,9235,9343,3531,9117,3533,7407,9706,561,3014,6807,5756,3801,5766,2888,8244,1057,2378,4981,9372,9590,1084,175,9850,7022,4317,68,6189,3582,3179,39,5854,4701,8727,609,1129,2498,9974,3312,3833,5626,1829,2952,709,7676,1061,5194,6629,6275,4586,5245,3750,9933,4414,3340,1818,5959,4336,1716,9601,2484,3864,7029,4448,4112,6070,5943,5760,1098,4053,7689,8058,4545,8598,6129,6878,4488,5266,1398,3387,6332,5432,6007,1938,2366,1214,3201,2180,1959,2809,5199,3532,8579,6215,9902,6394,3446,3716,3028,6716,889,2337,5133,6408,3307,7788,8981,8164,1708,521,3707,7735,8471,4853,9335,898,4144,7458,8254,7056,710,8588,4346,7602,8468,2902,5985,4035,2748,7824,370,4461,3132,1138,7071,3473,5767,5033,9208,1549,3297,2595,9176,4217,2407,5954,3051,974,2020,7289,7228,6068,6040,4131,9129,7019,4250,5504,2552,8908,6537,9492,2270,7953,4420,9880,5987,3436,8038,8262,4922,1159,7219,5482,1676,4462,1204,6664,1744,5089,2322,418,4789,8252,8145,7023,611,6037,4331,8847,75,5484,156,6589,3728,8094,5836,6767,8943,4772,8273,3890,5800,6227,7288,2648,4438,996,3721,5647,5241,5107,8295,4139,3541,7435,6086,1265,7890,6796,6091,5748,3113,6372,744,8406,3971,1973,4737,3463,2275,6561,4920,7041,5611,6761,6835,2876,9755,3925,2744,9788,9101,7118,4038,5889,849,9285,8864,2700,250,2110,8768,2254,5543,3749,1421,1927,3445,3095,9038,8640,858,719,9258,1229,2417,3918,4150,4293,8860,4838,564,7536,6898,6713,1382,8728,5568,9820,5550,3693,1575,7853,4474,9450,7830,6117,5282,6706,8717,4441,6474,9761,9216,2914,1209,4263,8426,3536,6914,109,935,4078,8161,6823,4066,5053,6798,9734,9950,8995,761,607,6294,1515,5456,9460,2993,1058,179,6612,1485,5408,5567,8015,7584,1963,4843,4557,3287,9635,9207,6690,3138,7685,6452,231,6344,8750,1835,8741,7008,5614,959,8858,9500,6276,255,2077,1509,5977,4285,3944,6757,5934,1075,9276,7970,9796,1232,9798,5704,4453,2749,6461,7357,7832,1470,8932,6441,5121,5360,2106,2997,7234,8232,1056,6715,6176,7329,1150,4573,1885,8836,2202,4936,2138,8888,1079,9545,7220,8991,6133,936,5551,2705,5975,6557,2977,5105,9919,6390,4497,4898,8829,3010,2610,7930,6273,7745,5592,1030,4061,6290,6978,4342,309,7755,5215,449,4067,737,1175,3542,8401,9745,934,1404,34,6730,1063,727,1713,6217,1353,7623,759,473,9201,5969,8134,5835,7468,1091,694,5405,8470,3672,623,1472,7659,9533,6376,8185,4641,1533,6656,8381,5644,5154,6370,7293,349,1380,8923,5091,235,3015,8320,3335,4219,4663,8189,1687,7239,2282,6406,5248,812,7910,3500,8119,9143,2303,1096,1300,2938,4054,9495,8367,3249,2954,9493,9525,9489,5254,12,8922,4974,2454,9577,5527,4804,8078,3923,9508,1711,5187,8216,5329,1250,1872,9524,3726,4042,7997,2292,9550,6292,7402,614,3418,6556,2112,3301,51,1858,1308,2078,2237,1789,913,9897,3847,4230,3904,9610,8347,5364,9358,7866,9678,2072,9980,3330,3555,7420,4323,9895,3348,8633,7530,2875,8420,3372,5921,1954,890,2479,9696,2535,4762,5628,2336,1839,7364,133,7942,8782,6162,262,448,2678,6871,1670,2194,7662,6134,3262,7744,7885,8453,4192,7454,4932,4728,6801,7809,2629,9153,2761,150,2480,3725,7107,2985,9213,6335,8281,5051,3128,9345,6353,7235,8731,5335,1331,7571,1454,7972,3108,5052,7167,2525,8340,3290,122,6200,3534,8298,6244,6119,5547,633,5524,2256,4490,1817,4060,9232,8350,4925,2502,3765,7786,3902,4519,779,5444,8827,7891,5883,2860,5670,730,7363,1856,4830,1491,78,2005,3857,9943,8428,6210,2830,9552,1297,1266,2184,1416,821,226,9496,2762,1348,2031,4524,3628,6576,7660,6245,4840,4518,830,7858,9786,1378,5588,77,4235,5821,6915,2309,1772,80,6651,1140,5094,292,7445,5321,2747,5485,5146,6301,113,3302,8230,4923,8043,4422,958,615,9018,5071,2000,7320,604,3273,5763,4816,8414,9010,2516,3078,621,5379,2179,6751,3684,5980,6917,6302,8394,7860,566,4017,2524,2975,3271,6135,4784,652,9570,6413,14,916,5630,3054,380,2625,6635,5744,4861,7377,793,7926,6887,4468,6150,3603,6338,436,6482,9659,2517,1381,5468,4751,8356,3508,9339,3722,9966,89,3294,4726,7770,3112,3289,2302,6179,6596,1958,6737,3491,6997,6611,2361,1484,3584,8174,7835,5779,1636,2584,7491,3466,2652,9307,1784,9556,1120,2528,7184,7719,2644,170,5150,180,2404,1301,3111,7529,3653,2688,3969,2501,8202,8224,5293,572,1576,7038,1369,8933,6739,7865,4971,644,1780,950,6428,3819,5186,981,5669,283,7516,3501,1170,2286,9374,7159,717,1487,2602,9082,2538,7933,2619,8092,3984,6127,6930,2353,5870,9466,8061,7146,2962,1620,8567,594,9152,1224,6264,8649,94,6550,4653,6728,9331,2211,6953,2701,6122,4883,4769,9260,4627,8988,3069,9627,6839,9504,9998,3120,4085,5025,6349,6087,1580,3202,8786,4580,4501,7590,7606,9180,7626,5816,8600,1840,9797,4427,1486,4334,7720,3422,714,8324,3702,5210,1428,5176,650,8889,469,395,1236,2107,4377,4354,7257,964,9252,6564,6834,5984,9781,8669,2805,9888,6830,6910,9801,72,4937,9945,1059,1341,8135,928,606,3186,9013,3188,1177,3620,7641,5088,7791,2141,5115,927,6188,2545,7460,5540,6004,1563,715,1216,5204,8445,7178,3416,7793,2646,1558,4865,9031,6319,6185,8540,9110,626,5570,2462,1379,8141,1565,8219,3141,8342,5393,7027,5351,922,2415,2899,8744,6983,6437,1083,7205,5571,4678,9237,4120,1757,8149,3377,736,8319,7595,8983,3706,1376,876,6771,7366,4115,7211,7535,5166,1219,3383,2018,1263,5765,6383,9125,6971,3332,1116,1344,7349,7385,211,6307,5586,4671,9000,1130,4687,6415,3226,6235,8218,7284,8220,4416,3545,8604,3842,6328,2732,4423,9529,2021,5538,3811,6354,1173,9336,5319,1414,3431,8056,323,903,943,3876,7732,5737,8499,8021,1860,9464,755,7155,8977,5865,3713,1824,2707,5185,6363,1408,9267,1014,9777,6792,4182,8353,2089,4359,2739,476,562,7604,3352,6526,3570,9430,5577,2927,2974,4698,3995,3360,1041,229,8234,4602,1049,6509,6054,7756,3892,3055,6889,8448,3264,1929,3435,7388,2460,9991,7447,4271,8380,8424,5873,8756,258,411,1975,2451,593,2348,7318,7588,6396,6145,1919,9302,8752,5087,1067,489,3472,8333,4107,1154,4116,2208,4363,6193,9311,772,3103,3430,7963,8555,3771,9023,9204,3469,1985,97,2995,9602,9640,576,1391,3407,2885,5336,5890,6028,7034,8275,6180,1680,834,8775,7774,6928,2765,5761,4943,3671,5729,2478,6694,8079,9735,3530,7800,7775,1996,1362,492,5143,4143,6967,4473,6774,2356,2573,8383,4195,8805,5378,4918,3920,8385,6051,4269,6925,3045,7443,1338,9506,7545,6279,8389,4419,516,287,4628,9813,4014,4834,6440,645,2471,3317,373,9392,4188,5313,5141,5197,1193,3853,1145,1363,5433,4643,6156,6062,3882,6254,4705,233,118,5728,3060,2505,3225,3930,5627,9172,4866,1248,3459,192,3644,9244,1581,2837,7771,7191,422,4630,5298,7387,4582,363,5434,7787,5903,4358,1825,6505,1496,5280,656,1550,1905,2343,6572,9203,4738,9840,2458,5557,4719,9024,6883,5695,7581,1375,2591,1200,8467,1928,590,5286,2035,1628,3938,5157,7561,3155,7932,8663,7463,1326,3566,3601,8907,416,9951,1865,4352,4118,2499,3710,596,7684,6347,531,8582,8733,9989,1560,9145,7965,7207,6216,3962,2330,9086,2725,984,8843,1810,9605,3748,1171,2846,3631,6546,3936,5927,9833,8194,171,6993,1283,3643,2411,3151,3022,3535,9112,1672,4616,4425,4274,4183,6724,382,5555,9288,7398,3668,1160,1165,873,8594,2301,4857,4158,529,6685,324,8699,5755,6074,1208,1405,3680,4917,8770,3254,2886,366,9539,5981,643,2310,2998,2129,9702,3223,3003,9107,544,2724,7255,3758,4309,2578,3324,3807,5013,497,6444,9133,332,9137,4095,2820,3718,657,8883,8703,5092,8893,9968,4380,3248,3823,802,3238,9375,8318,4608,3351,7333,7873,354,2155,4194,1323,7753,1967,6818,4520,6029,3397,3255,8987,5566,9228,2511,4236,799,4670,4262,1833,7979,7277,9312,2483,2421,4319,7043,9976,6239,9291,2305,9606,1874,4335,6605,7501,2066,10,546,1965,4259,3502,8208,1748,5986,857,8978,4787,6961,442,7924,3968,1852,2793,8664,8918,4109,6240,624,4912,8404,9905,6207,138,1504,6669,3067,2287,5509,6745,6754,3032,7351,2132,47,2340,7985,1125,6911,2375,6860,7931,2931,5037,7365,2218,4072,6521,1328,4044,2600,9093,2166,4652,6554,8971,4730,3031,7839,4240,7826,7229,8293,5822,4841,7035,6143,6986,5694,8525,7273,8451,2630,3778,1626,7643,8355,4977,364,3136,6401,4739,7949,4412,5247,8591,7459,5848,2868,908,7821,6031,1111,8687,4231,1409,3703,4284,8314,5583,3891,8013,5192,9140,7031,2582,8508,6658,587,1535,9501,6182,4242,8666,2159,8996,4373,9642,1218,6470,914,4213,8787,157,5118,7408,2371,7451,5511,4433,7360,503,6775,5029,3756,2199,5503,9158,3941,765,559,8681,6096,6780,135,618,8632,6840,1133,7596,7012,9314,6553,3742,5852,4869,6030,9406,2958,5191,4184,4664,8507,5255,2219,8104,8469,1047,2365,2469,9132,3592,8547,1588,9062,3097,478,6181,2877,9351,8698,3625,8372,2737,29,8376,3204,9695,1904,4151,911,338,8870,6327,6186,7845,6460,8961,9629,9510,2376,4773,19,6566,5404,8490,7849,3551,7389,952,6356,1222,4847,2513,4320,9615,2844,1009,5235,4945,577,968,5079,7593,9002,2269,5190,987,9961,2537,9932,2570,9142,6242,7119,5123,5858,6922,5742,8427,5034,9494,9847,8825,9051,2930,7544,9274,5011,7852,2115,2874,8520,5613,5792,8396,1060,517,203,1361,2784,9325,3717,3844,3413,9150,6043,1357,6291,2643,6219,7609,5842,4051,5036,662,8118,3479,7484,5260,403,206,7962,7874,8675,5654,3841,3220,8910,9197,8838,5919,7301,2946,513,7794,2772,9878,1354,9472,6371,1769,8496,5775,4740,8484,9600,2426,9832,4877,5168,6974,7784,5064,6927,7605,3084,4812,6764,3268,8017,7668,5526,5285,6822,1596,290,5978,1804,8378,5272,1006,361,7923,6691,3293,9378,4315,4016,2766,7564,9622,6183,2064,8949,6050,1389,8370,9263,6851,3546,8157,4460,5574,318,472,6573,3006,1878,4836,9004,7039,6836,8494,1052,3217,7812,8715,6352,3775,6101,2095,202,4032,1953,8379,920,6095,9366,9478,6105,5606,1706,5642,6109,7428,7587,9040,3449,2120,725,2704,9259,7286,1728,2060,6270,2873,9693,8142,1519,8329,7887,2496,881,9447,6485,8237,5085,2338,4750,3651,3840,768,1536,3767,33,1990,3442,210,1315,356,5500,3835,4097,2102,8722,864,2200,4631,2620,6600,4712,6293,7710,7531,6247,9070,1863,7558,3963,4610,4666,832,1477,5680,3846,2989,1583,8146,1155,9941,639,1553,8483,6055,4521,8631,55,3259,1051,1106,7537,8297,2255,409,8031,3305,6009,2123,5213,5508,978,4910,6727,6826,2006,3206,5464,5532,8481,3398,4500,7202,5304,5807,254,2290,7654,4988,3611,8865,9667,100,9022,1212,7955,7727,2140,6234,2769,5018,8124,3415,3522,1099,6497,7209,5634,6431,3575,2622,5556,7709,5193,9699,9587,5925,8937,5465,4959,7729,8832,8392,3090,2661,2410,7151,3635,8138,3130,7247,3967,4622,2325,6487,5513,8570,6558,679,8726,8638,1617,3148,2675,5605,5805,7412,4961,4549,8611,4614,4098,3513,9246,5108,3092,7370,5974,9837,7467,5382,2994,4950,1561,7136,4607,3056,6919,8400,9774,6677,9079,9077,3316,5788,3986,4348,875,862,787,9319,6236,6858,5473,828,5443,4673,9722,7221,3074,4656,413,9873,9369,1851,9939,2978,2182,774,2554,8005,4512,6904,5692,4953,6525,5841,617,778,5288,5651,4899,2272,4757,4275,7004,6251,4919,5239,2854,6046,6571,658,28,1564,9294,4592,5438,797,4452,5306,4034,2982,6161,5271,4588,7153,1490,1700,9860,4574,412,446,7448,41,4661,2030,2703,7917,7810,3852,3845,7456,632,2402,8680,2904,2757,831,5746,5294,5043,8998,3199,3083,1962,1488,9149,7276,5960,2649,8952,8285,1893,1492,1892,8425,6752,7437,1141,9036,1586,9744,3856,5914,5163,3096,4587,3168,3911,4318,187,8628,4560,6066,4389,49,1272,1364,7457,4600,1827,8242,2923,1675,4636,4907,3633,6434,3573,631,8083,1335,807,3170,9199,3490,5829,2559,6026,7511,512,8688,4806,5387,1123,7848,2395,8821,994,8241,4795,2094,896,7586,6979,3908,1213,6545,8629,1473,9709,3236,1914,9523,9457,6692,2645,6892,6536,1451,5738,5515,2631,6762,9620,223,8619,1890,9660,2250,2206,6512,4451,9703,20,7452,1589,4406,540,7016,6579,6591,2261,5220,4221,8432,8250,7204,9650,6994,758,5084,8107,9194,3004,6540,1101,9675,6640,4094,8777,9616,9760,1089,291,3089,9035,7781,4340,7258,1012,6389,2441,1153,7986,9792,4122,6695,3210,5315,3901,1859,5625,3677,9988,8458,2858,2917,9793,4446,6698,3770,5826,9057,1429,3178,1029,6056,4041,3764,6977,8605,5440,182,2070,6734,538,5490,4649,3133,2760,7900,8289,2252,6111,1517,443,1801,872,6197,7206,7444,1635,1180,2086,4888,3123,6787,232,3020,4104,1704,8303,6519,7691,9875,4690,1759,2052,2240,359,3139,9927,7999,2466,3738,9928,6449,6153,191,4483,102,4658,7803,8531,9987,1645,4960,9718,5007,4722,5899,6747,2422,6577,2548,6283,9538,1732,8140,317,6053,3258,708,4724,6358,1124,6522,2635,3025,5909,3769,9316,9663,8168,9977,6351,8360,1642,6697,2588,6410,6504,8026,556,5559,5667,3683,9066,2222,3621,4723,5806,5923,2856,2663,6006,5778,7200,6044,4604,4502,1430,3265,8053,3299,7079,9576,8121,1826,921,2379,1393,6861,3943,234,9175,6357,8853,698,3698,796,9078,9802,7323,4129,4125,1730,4260,9712,5307,6067,6361,2782,7677,1842,3455,7991,1587,1786,3744,625,7844,3484,4721,2959,4566,8869,7137,496,3512,3114,4214,321,6547,4325,2042,1941,4168,2294,9962,7319,7309,1249,7914,3485,5058,9975,5535,6141,4225,7672,4421,2400,4532,9016,6832,4507,8365,8569,8332,3125,3363,9299,7675,36,9411,4429,3105,4401,4025,6789,3737,5580,143,2062,3701,1997,6693,1921,8310,7682,9296,782,4781,8062,5287,7599,637,4374,4216,764,1466,1658,6281,404,7763,9445,8566,4954,2786,8576,1437,9114,4447,7823,7555,4418,6013,1663,7310,6337,8306,1352,6655,5904,3216,2446,8534,806,9393,3331,2246,5688,7630,8882,8766,4759,9859,9212,786,4030,3292,3480,272,7876,4829,4266,7399,5676,7901,4287,8349,4161,5077,6269,3641,1169,199,5429,7904,8437,6808,4842,8462,4434,2185,2236,4037,9756,1848,252,5657,848,5635,7504,5119,9262,1016,8267,8456,2212,7880,1816,8188,1223,4186,826,2613,5711,4008,8885,6490,2445,8612,2295,8783,88,9940,9417,9098,8572,9488,2278,1651,8348,8486,6343,466,6825,7742,1760,6132,5799,1673,18,2529,3140,4077,1901,749,2929,8028,164,5957,3903,4785,4000,8160,4856,9926,4546,8679,4699,5665,1205,7950,1714,9807,4609,3100,8595,5358,8,1276,5348,7337,8030,7069,6735,1541,7476,4361,842,421,8511,6409,5251,4364,4599,475,3650,899,9254,7000,207,7296,8684,3781,9156,3662,5810,7180,7254,5399,7694,9920,5370,1316,8037,2836,2032,6059,4040,2593,1340,7598,9821,9747,6534,2894,8909,1695,3900,4991,3033,7047,385,1424,5777,5330,4177,2826,5787,3966,2074,9426,7652,3224,8902,3365,8648,9592,3064,1164,6646,7042,8415,568,5510,1500,4896,3219,8116,4688,8592,6224,7591,1602,7747,9169,4467,1151,2432,6729,8574,5145,8796,3735,7508,2604,8667,3893,4632,3618,8007,9558,5781,8029,9081,8589,9011,9565,6924,784,2862,8339,7702,6949,5232,3406,2541,7552,6391,500,5002,4957,2774,6036,5375,8322,3282,4332,7169,1709,3960,7068,9281,6035,9266,7636,6942,4731,3116,8251,6803,3311,909,6705,2795,3478,9839,8510,3646,961,8536,9270,775,1017,1649,718,8422,6311,8036,4237,1290,2767,5840,3421,8129,6021,8321,6178,7569,8101,119,9713,3373,3848,8674,4650,4013,1303,195,3328,1805,4493,2492,5126,9819,1503,1122,7342,9555,4833,1422,5140,2865,5367,2913,9303,5132,1546,3559,3586,1977,2034,2394,3058,7,3167,6137,3496,6453,1513,2413,845,2612,6177,1467,2104,991,2203,6722,3954,3253,1821,2596,3404,7760,8412,8132,3101,3800,2638,605,7440,2424,6011,7327,5601,486,2543,5897,1877,458,5861,6429,6644,3230,7104,9923,4523,8074,7977,9947,1227,9764,8581,4541,841,2215,3456,390,2587,3896,4805,1168,9730,8656,7065,8148,4894,9794,2979,4921,9116,3026,5639,2280,9804,420,9727,811,810,9160,9490,1281,686,690,1895,1559,222,4931,54,2515,4872,627,4929,2390,9073,8596,1555,4169,6926,316,967,136,1311,2362,1610,1773,7433,5796,3338,6590,9214,1158,1611,7528,5859,6944,3759,2148,7367,3673,8571,955,4598,1070,1657,5045,4454,4027,4859,6464,314,2459,9467,7507,5218,149,4778,4639,9959,4871,2195,1686,7082,62,1838,4124,7455,8050,7982,891,1947,7954,560,4969,9885,2186,4114,3776,4629,2114,9268,6931,6342,6937,4386,7534,6847,5956,8409,9292,4646,6535,8645,9854,5717,2346,6483,4796,8034,111,9394,7560,8126,221,9330,137,1332,9549,4211,7256,5182,3539,5869,3184,1507,6382,8433,9921,3433,2601,1273,589,9135,9531,82,9346,6411,8665,910,9217,5710,1305,5212,8269,8336,2562,1139,2191,459,3457,5171,4185,1524,5713,9234,1737,3426,2957,265,3899,6252,7748,1917,781,6782,1955,2617,5135,7303,7701,8790,5311,906,8735,9048,2288,3828,3358,4803,677,1763,1048,3380,7894,4892,8282,598,7464,7300,8873,4591,7101,6912,8358,2810,341,9724,4083,1659,6093,5014,2628,7145,7481,3283,6124,1189,1001,4825,9387,2936,1178,391,2889,121,5263,5346,8707,8351,654,7807,5638,6679,8464,6147,5291,6374,603,7182,1682,2339,2263,6257,6296,4562,5845,9848,2311,2058,4327,5368,7514,9484,9586,8175,3304,8223,5198,9196,6259,6530,3587,5619,1900,2706,2044,8500,8990,1778,7939,6316,494,2804,5621,5758,5633,3931,9428,2342,3269,9097,3867,326,8388,2709,4851,3836,161,9167,8514,9597,7827,1411,8454,6895,6896,2939,3914,8868,7616,7144,5431,8473,1226,209,5008,6711,4299,1262,9461,1674,7212,9655,9547,6523,870,8912,3048,8650,9867,2453,2898,5006,7482,1510,2001,3755,1406,1733,7115,9509,4506,9548,7911,5274,5972,1128,856,3115,3953,1210,8702,9383,2121,6975,130,4209,3687,3156,4043,9376,6678,9578,165,6322,1246,6318,6260,1148,9572,884,1770,2307,2941,1956,3346,464,2241,3122,957,8240,2792,5365,5308,4153,2662,5672,6663,8233,5932,7671,2798,9541,865,753,6289,8341,8607,6310,542,3375,8972,4565,6569,7525,9261,8718,4179,9783,7679,3408,2318,4189,526,7948,347,6398,2817,7201,2585,5445,9948,6287,7415,6769,9649,37,1339,3544,2249,2008,8073,5447,5824,8335,693,6405,7405,9569,2037,91,1069,4289,1931,6100,9996,9146,7615,985,8387,1192,4024,4814,1880,8463,1834,9879,532,6108,9845,1103,2015,3172,8671,1032,7686,8992,790,4714,7087,6304,3091,25,5458,4618,2081,9972,8247,983,8287,9758,1360,1468,7014,4117,2450,4002,8343,6793,8180,424,6813,9409,2807,345,2164,3994,1879,43,703,181,3325,2108,6467,3747,748,5811,2673,8745,1456,8368,1025,2853,6466,1286,8354,5086,6237,7465,847,407,79,5155,4047,5396,8263,8661,1800,9127,4375,8195,3243,2605,6779,2491,7347,1021,2879,7330,7070,6721,460,918,110,1945,6225,5305,8818,8986,4062,263,5990,3754,7585,8506,9789,7559,8690,4900,1302,6760,3809,8622,8191,1983,1538,1590,1260,8740,2457,2465,2970,5233,3279,3652,428,6633,1522,3319,9716,9969,9380,9952,962,9233,4,5246,6821,3187,6884,5828,5948,11,4794,1566,340,4890,2207,3053,5,9099,2867,3334,9359,3913,2722,2172,2357,2385,8599,8682,6123,7497,7409,7226,9994,5196,4045,7338,5996,1288,8603,8643,1366,746,9365,8144,64,6791,7980,2906,8305,557,2127,5973,3240,1882,8759,3322,3829,648,4415,331,4855,3989,8647,9598,4252,3315,4465,433,9732,7051,1592,3964,8106,1071,6784,2447,8863,5739,6582,7017,2915,2387,6472,2293,1570,5794,783,6387,7265,8200,9684,7813,1157,584,8009,4867,5466,8497,8143,7287,2720,9841,6407,297,8277,1807,5949,6623,4760,4624,548,8266,74,2835,2719,9069,581,5662,59,9528,9557,1936,7103,2358,27,4951,3439,3883,1434,8480,9740,2036,7639,8317,7527,4765,5843,4810,2124,3117,2038,6962,2253,4330,8091,8452,5122,4475,1461,7037,3011,5470,9580,8799,7223,9869,4554,9103,8897,8214,5645,743,2386,4028,8739,45,1481,2509,8294,6489,2940,6061,8831,8969,7765,4942,9256,2243,8068,7177,7499,2162,2987,9407,2967,9588,823,8133,134,438,2824,6250,6404,1989,3619,5849,2878,7966,8182,4555,3207,4347,3447,1372,3999,8311,9990,549,3580,5070,1220,7831,7328,7340,3924,9856,9723,3344,6491,2680,7789,1734,1974,9542,6034,8173,9413,8720,2416,8939,7759,4385,6603,8441,2937,8513,2901,4863,1388,4180,9441,2098,4732,6246,6042,4662,7311,5819,2951,8719,115,67,2046,9122,2764,728,4997,1871,2660,8418,7678,1450,8947,3093,942,580,1942,3763,1312,7230,2013,8429,4367,6149,346,9751,2679,1966,4561,9499,7855,4404,9942,2291,5815,4799,5491,754,2444,5773,689,9981,6622,4205,8246,3802,104,2440,6814,1494,2569,3760,2007,534,5983,8816,4967,2354,2671,2160,9646,4297,1855,3263,5067,3313,6090,24,7619,9741,6863,8563,1471,249,8060,2674,5436,798,5988,8344,7092,2398,3720,8602,7736,467,5582,4584,6665,8434,4096,9978,924,7013,9720,1634,7077,6388,8286,5363,2895,2743,7493,3712,1431,7708,7877,649,2815,4793,6419,6933,9544,1684,9575,5783,5324,9808,4681,7869,7268,8562,3278,6501,465,7578,2136,5795,4379,5608,1978,8018,8155,6819,5900,9679,4409,6849,8914,9396,2487,2579,1694,4004,7553,6636,5419,4927,6632,9692,5028,3233,9759,5958,1275,2618,3386,1000,5585,5112,4202,9126,9502,6148,8025,2373,2866,4227,1108,7749,7699,3547,1313,4963,5406,5808,3561,3061,3214,9896,2099,4711,963,9697,4700,3910,1019,9361,2234,1497,4442,2111,2257,3309,1875,9094,7538,4801,2850,9434,3997,125,3158,9124,2695,4499,8915,2401,5576,970,7134,6157,9087,3049,3354,6799,2670,9870,1836,804,7843,4665,9037,3504,5156,8403,6256,5961,8807,5327,9630,4548,6019,7922,6214,1142,4503,3420,7299,4572,8734,1478,8461,2209,4368,4052,5599,9381,9121,2382,8027,7315,5142,7568,2718,7969,2019,7335,4165,6575,8047,9503,5026,9953,4471,6743,7711,6112,1793,2004,4835,8597,522,6168,2317,5945,3947,8070,2494,1999,8475,2239,6810,7331,2156,5675,1480,3173,6160,7629,2565,2128,820,3851,1294,7996,7806,7240,8676,4682,4887,5459,1568,7515,7199,9863,3821,3024,8625,357,9944,579,1024,7026,9190,2175,1854,7816,7738,4996,7139,1251,2825,7841,5275,3080,5240,5425,9165,9986,6229,8724,1822,5830,3518,9438,2984,5593,8413,7857,8830,4160,5460,5202,2105,105,9315,3342,5895,6855,6130,3521,2518,386,8117,5188,1853,9882,6144,4417,6263,6422,1050,2755,599,426,2154,224,9526,4621,3817,3624,2693,9415,992,4693,6473,1627,5295,4992,1003,1179,2696,3277,5250,8272,2590,1678,5610,6620,8235,9219,7978,822,9355,8837,8794,2389,5786,248,6950,6315,2117,299,1412,2233,1427,3379,2586,5453,3205,5318,126,5955,7314,7269,3808,5109,4050,6657,835,5005,8265,3356,1790,3000,5939,9965,4504,1447,9151,3227,8738,6544,5753,4709,9163,3008,8131,8769,9348,3979,3515,439,7075,7968,3437,5359,5022,6520,5334,7291,6957,8206,2334,642,434,7485,2776,5201,190,2026,7094,2029,5727,5776,8700,8478,6759,6439,381,6920,6843,9956,9599,4267,3792,2742,1787,6875,2561,6963,1779,4779,655,4952,7132,4370,6340,3367,671,4747,8577,2142,9353,3359,2442,8447,463,995,7427,5369,1309,7434,5724,5038,2474,5020,8040,8014,9698,2851,9210,2756,6369,3428,1184,7506,5542,4075,9033,1632,8542,3417,5389,8552,4407,32,4444,4397,176,7488,1982,2143,510,6804,7828,3571,948,7881,8276,575,9293,1971,3830,8304,9007,818,1717,8764,5493,6661,9901,5090,6841,1261,4255,4111,9053,5935,692,6255,261,1781,1085,8016,9823,7152,5244,7001,7138,6833,7883,9834,1092,3361,4782,9799,9241,8791,1287,5283,3145,3152,3975,684,7998,455,4498,2320,5004,5791,3694,8736,4033,2328,8658,8841,4155,2783,3940,2277,1318,1325,4889,3470,8001,5730,9865,8008,4749,9049,7368,6000,5991,5391,4265,257,6959,9930,5362,52,8820,3295,7356,7761,1457,8886,2276,6314,1525,4831,1100,7088,9633,6495,495,2882,1499,1718,9862,8849,2519,5979,1594,7902,9297,2508,8746,4273,5361,8693,4402,7973,3039,9658,7306,9661,3427,4058,8662,6385,3349,4612,2093,417,4469,3870,7185,1909,2214,4617,5442,722,7547,5410,3528,4073,4432,1239,6125,3076,3745,2891,9474,227,5522,8524,4489,1939,3524,641,1182,9105,7681,1648,1336,8642,2144,5312,6829,5273,2734,1930,4774,3982,213,5992,8128,5423,4005,1866,1950,3972,9826,8006,5594,4208,4113,8519,266,9486,4903,9321,1186,971,16,8163,9324,989,8583,7174,9665,827,3607,5078,3411,7278,4339,3600,8488,5643,8709,3005,9520,1435,60,7646,1943,2572,9363,4399,5017,7783,7494,9440,6493,2547,6820,839,3615,1479,397,2351,6071,2991,3257,302,6203,1483,5928,3012,3519,4291,8850,7627,15,1783,3474,7236,9248,2085,6973,5414,3471,8227,5520,6359,6223,2131,4484,6708,8123,5129,6518,3403,8495,9453,1385,4261,840,3818,9874,5317,9341,2884,6375,809,5661,3909,7690,7432,1600,5855,5716,1844,169,7441,2717,4620,9206,3160,2050,3935,7175,7055,8639,5012,4815,2681,3788,960,3695,6634,5646,1299,7147,6024,5689,9179,310,6295,9356,6674,9674,499,8811,7819,131,4362,9323,9568,389,2083,712,9671,2503,50,3782,5377,6492,162,1944,3102,803,6463,2349,1771,6069,8221,7217,9242,6312,7393,5376,2061,9433,5355,5590,2025,1910,1815,4020,8369,9757,1608,6597,1937,274,5879,8313,1755,2557,7411,9224,2523,6838,3727,2139,8080,735,9271,7566,3647,1820,6209,7524,7767,2396,3569,8951,98,9063,5046,6638,8614,6960,1796,6477,4780,183,1282,1767,5259,667,2841,8899,8712,1345,66,5702,3678,1495,1521,9352,9543,7176,9310,2808,7878,242,2223,5340,9318,1023,7438,951,5110,2852,2563,1731,2981,1162,6114,4166,339,5839,1346,8696,6438,1013,4986,6659,1152,986,1775,1615,3642,5963,2216,8634,3806,8578,8683,217,4668,2794,281,2118,732,5035,2948,1527,3955,1619,6541,8802,8212,9624,9858,92,6583,7700,2813,260,173,387,4808,7470,8345,7715,3337,5906,7285,7403,5104,2603,6905,7868,4882,4980,2181,7046,2632,7213,8732,4223,9159,5467,9583,1979,5054,8225,5541,5161,9357,5530,6529,6969,3161,7651,1741,427,4439,1808,8443,7439,3996,2676,7396,3235,3007,7168,5514,6115,723,5474,6306,8102,5785,6726,1135,9993,5074,4745,5780,9690,4191,8405,3529,2103,3585,854,1028,1753,5528,3098,6366,2433,4651,6563,4578,3942,9249,3066,4823,2262,6702,8533,8754,4852,6447,3451,9815,3274,2636,9039,5471,528,1274,8130,5333,9236,8677,9516,9852,9772,3029,6601,4791,8558,4197,3875,4886,1238,8774,6594,1026,6653,3898,8063,6284,5021,2134,8618,1419,7633,1115,9275,8713,5478,1502,4915,3961,5703,563,4654,7915,8162,5219,9257,520,1289,31,7096,1516,8548,5666,1579,9240,7648,355,8609,9973,4595,5234,2890,5441,4820,8485,6299,4978,7416,2731,8096,8136,5174,3880,8391,4797,2992,2368,7928,9442,5910,1992,4911,3071,9119,2242,9178,7374,4215,9844,6468,5699,2314,2049,1156,6274,5439,9027,8835,9131,8761,6717,8158,5448,6943,5487,9471,1785,6172,5677,6608,8386,4845,9641,9800,4088,1940,5913,6329,2232,2966,4472,7730,5125,570,8150,2467,6423,2861,3343,4556,6300,311,3594,3638,3434,278,277,7125,535,4683,2745,9334,6817,8765,2685,7517,8256,172,342,8261,4516,13,8316,5483,3734,4199,4505,5690,5774,3527,2694,2699,6733,8834,1604,7122,6788,6222,3739,1654,8154,9688,9100,8884,40,7938,550,5989,7632,5430,1968,3766,3448,5152,76,4569,3660,7906,5277,7124,8872,946,6940,4534,5249,7603,2711,1811,9626,5032,6683,7740,1392,116,8459,5579,8172,9908,8856,9015,9829,3385,2370,5421,6614,4074,1994,1508,5223,2504,7242,5116,4755,789,3458,2076,4092,4212,270,451,9269,5231,8299,1443,3333,5338,7161,4126,3610,8065,2408,7325,552,6874,9636,2690,8958,4277,8171,225,5578,713,8845,4298,322,1076,8789,7688,7634,3540,1884,2822,8231,6298,1552,4099,4648,9423,7975,9371,8753,8848,4948,7653,4121,6484,5673,8113,5069,2691,1896,1254,670,2427,9247,7862,5455,2544,3321,3256,5624,4313,3868,937,6670,7739,2377,1629,4304,706,6082,1573,2220,4011,2430,238,2113,9871,2452,241,2510,9672,4807,6386,5350,2284,5553,9913,4854,4964,9955,351,3888,7539,152,9883,9465,8064,3974,3394,597,2205,5997,432,7336,1685,3013,1040,5415,4470,6272,8948,9518,3753,5310,9893,4408,4916,3865,2821,4862,9111,7734,5884,3689,372,5386,2173,8109,7380,4802,4511,4207,4306,7446,5488,4744,1068,5207,7951,4968,6682,4175,9997,7466,296,2512,4057,2621,4716,6267,6507,7471,9623,5632,7108,1661,4064,2556,9817,7840,3665,2065,7892,5617,9422,979,9009,3669,158,9322,8248,5802,816,6684,485,8529,1112,2881,2493,7680,8081,5912,5300,8940,1330,474,2204,7021,2536,4972,124,7362,9497,5837,5745,9164,8965,4026,7072,6435,9326,6648,9130,1245,9120,2335,3190,8968,3401,2210,2289,5733,7067,6958,6935,8984,8057,8616,7842,5693,9775,9344,8328,5102,6469,9753,5136,4393,4597,6795,524,931,1705,2928,9250,7725,7033,5812,194,8492,3636,7193,1907,120,2380,3144,6266,1774,6175,7808,8800,468,5752,8264,2790,3622,2999,3376,525,7583,4157,1476,2791,6479,5754,2814,6921,2490,140,96,6642,8545,3177,4256,9982,5177,4222,7304,3241,4846,8823,9045,3495,2802,9092,7642,4479,5149,1639,3009,1662,8575,5290,7060,3729,3699,5918,7074,8606,2839,7172,4383,7687,8970,4322,1846,106,2568,101,5569,504,3576,6416,7375,376,5424,3956,2059,8449,7261,3393,7833,5790,3543,9286,2177,4176,3666,5801,6514,3023,1650,5655,147,3850,3796,2055,9337,8797,6060,6906,2056,505,2983,4018,1697,1530,244,8840,3825,7790,3743,8528,3700,8966,7010,4674,5049,4763,7500,1961,3503,1894,5887,7225,3438,7622,7707,8737,8346,905,2976,1933,8352,8710,1,1439,4430,8751,6333,7495,6201,6400,4710,4735,6982,6433,3577,878,8435,5950,9949,8580,1231,801,3736,9654,3088,5494,3072,2560,8803,5533,7805,4463,7149,6233,6599,4009,3169,4579,6158,773,4669,895,9639,3250,2217,4551,507,9139,8362,4206,1993,8767,7751,5901,9420,3884,3784,4891,8410,7085,6020,9328,4101,5951,8196,5214,6243,8721,7882,481,9264,95,8804,3237,6014,1054,4108,2576,7692,2763,2069,2423,7644,2221,2178,5227,1777,6163,3085,8258,9750,7927,271,214,1163,930,7645,1647,3414,3985,5502,6341,1394,7442,2780,7956,7461,7897,330,5343,1902,8653,17,8323,874,9855,5536,3157,9681,5894,9287,3047,5993,2183,2167,5183,6995,163,4296,7030,4906,8851,5709,6159,3345,1609,9752,8438,2090,1206,2146,3424,1498,4788,1465,5225,6308,2818,9047,5457,3723,4581,4349,8024,6732,2723,3347,1870,9403,2686,9877,1597,5603,6602,4706,5211,3568,3082,1230,9726,7936,1867,4388,3153,3664,7829,8550,9295,7994,7704,7190,267,6630,1883,1698,5809,9625,2406,9012,2950,5668,6618,933,674,9226,3686,9452,7492,9421,6151,1007,3191,2244,5597,9342,1351,4486,5371,4201,2803,4487,5309,7510,1104,3560,8695,327,4300,8819,8651,1762,1144,5971,3843,7449,1066,4533,2553,6170,9,5534,4514,2014,4257,3232,188,8186,8268,2344,153,2773,7674,1399,1832,4162,8066,3572,6005,4962,866,892,5581,2428,4449,3384,9763,8641,1916,4924,640,729,5652,9192,7837,9456,4848,7697,3574,6758,4171,7490,7758,2198,4081,1418,8941,777,5750,745,3336,197,3564,613,8489,7601,5922,7664,2326,1577,4926,8725,6450,6228,5040,9618,5529,8621,5412,5722,1664,6891,6199,1906,437,300,6002,4400,3696,4821,7162,155,2047,9485,9154,867,6471,2101,7373,2942,7957,8973,5707,9189,5170,4021,720,514,919,3018,5518,7316,3589,7520,9890,9273,9096,8491,127,4337,3523,8290,1390,1247,1436,3275,5314,663,6154,3419,4105,1237,2393,6458,4633,48,4141,7898,7002,9964,1432,4999,2161,444,8613,9419,3452,2463,5609,3369,9822,2391,8793,7430,7850,6617,673,571,141,7005,4046,5933,4526,616,2753,5407,7799,5226,8523,6305,4102,9937,1042,9831,638,2063,9787,7270,6766,6418,9638,6427,6285,9645,5047,4443,8711,7513,1534,8743,1243,2526,5740,8670,6989,6516,6265,6142,3194,7713,7728,1167,9020,687,555,7937,9579,1908,9958,5354,7625,5544,6893,9280,396,2039,1334,6649,4596,5476,6195,5863,8828,9362,1368,7762,6947,2485,2150,6539,71,46,3126,9708,6964,9924,6001,3937,1912,5734,2741,6213,7251,9412,7903,4036,676,5823,4930,3987,5057,2580,2614,4254,9161,8921,3182,9431,2135,7376,3741,5075,2514,9106,8704,4874,9668,539,1582,8450,377,4264,9071,8371,4394,9443,1518,3077,5117,7112,565,4091,5558,7332,4100,5715,1665,6022,7049,5537,4071,1812,1190,3378,2945,6873,4015,2972,7160,7111,5042,5489,7018,2657,7197,4764,8685,4127,4345,8928,8931,1321,2916,9707,5708,6424,8498,7192,4939,6380,4396,2151,7241,9691,401,3981,3486,461,9694,4496,3614,2961,5623,6038,956,7157,219,9670,5936,3440,8623,2520,7920,1641,2258,8089,583,8895,6231,3993,7462,7502,5874,8515,3810,8814,9147,9308,610,1585,9186,9849,6010,1512,1252,2082,5885,9589,9910,3965,4170,6140,6543,3134,8747,7123,3733,5435,4082,1520,5782,3813,9992,7227,4752,5372,6194,3626,362,6476,7187,8808,6765,3405,619,8549,8925,2367,1203,3878,5880,7944,6339,1183,2893,9128,6890,3674,3364,9157,1015,7208,7541,7410,4708,5400,8213,1843,8813,2623,819,2708,7554,5031,543,8546,6897,6241,9482,2225,6164,5081,6880,9522,5055,3150,4965,553,7252,6586,3286,5658,9768,3362,5326,3834,2011,3675,7797,304,6089,3357,3656,117,5124,1652,3511,669,4880,9432,7050,6080,5068,5165,8624,5965,8199,4390,5209,6584,23,8054,5059,1202,1976,7487,3952,6211,2654,7312,7647,4684,3719,3175,7006,9046,2193,7128,925,2306,5237,7987,2880,2606,3731,7214,1448,9454,4174,445,2812,2968,8862,6128,9685,3946,9470,1207,893,2080,5714,7526,3537,7414,9766,5003,3465,9651,9222,350,9872,4934,8644,1656,1514,7989,3350,8112,2665,4509,3052,2920,882,7216,9748,8859,7279,9390,6939,886,3461,5178,8942,4232,2571,7498,4811,5072,8672,1134,3396,766,6286,8723,9221,1688,2355,2403,9894,1814,7400,1027,369,5208,792,2324,4640,7861,3464,5426,9728,6948,9999,8527,1267,5871,8399,2333,8957,2911,415,554,844,2754,2827,2054,7015,3432,6167,724,1618,4676,5732,5660,3602,8551,7305,2412,7723,1644,1616,6136,5103,7556,9546,5060,4729,2781,8482,6442,7854,1396,975,9743,4063,9909,2323,6877,477,6075,7614,6688,9155,3163,3374,7519,1692,7522,8465,8279,6,7613,523,4023,2281,251,1754,3040,5589,2653,1646,480,4553,9619,3838,5636,9613,3514,5803,7610,2702,2251,1864,3588,7076,9717,7194,6206,635,3657,1377,2980,5258,8553,7856,6012,8152,2264,5653,7655,3285,2912,4292,8011,9469,3751,6720,2313,2921,200,6323,4946,8608,2051,4006,4786,8487,4405,1242,9637,87,6965,2364,7343,305,5886,7171,6749,980,1046,1980,2315,1751,794,7116,5924,8584,2224,4543,1343,5499,4238,2672,6941,3640,4294,2840,3874,3371,5917,3222,8512,5747,1460,6714,6456,7195,9715,8673,2925,5477,6326,8423,3538,4697,6538,3341,4606,4619,1726,900,8395,1347,5964,518,6268,3604,9368,7063,8187,6595,8994,4138,8879,9414,4742,1255,5833,3630,4398,4914,8375,5505,3300,5065,1750,7489,6631,9001,1161,1285,9058,5134,4302,4426,2715,9360,2849,6155,8854,8331,3425,4822,8706,5265,1350,6934,7543,2642,3746,6113,6218,1828,3639,5341,4328,6499,8072,682,733,9427,9463,1349,5562,2779,6103,4279,6436,5793,3774,99,4995,620,3849,7836,1367,2870,3623,9866,1475,4508,5549,3164,2871,3079,2848,4055,4692,8945,2331,5076,6126,8655,6528,3663,5847,6475,2828,1889,1819,6615,367,7768,2304,4258,6454,2468,6212,6876,3907,2801,1554,699,7557,9527,6084,6049,5452,3824,1949,3059,1080,2729,860,5962,3460,7722,8002,6063,5270,4234,4593,7345,973,9424,7020,7717,9300,1913,9085,4570,3081,5437,8953,2847,6131,3752,1935,7346,1655,8110,7673,8197,9687,6588,1756,2350,7777,6465,8084,8871,7579,4876,6271,6768,1571,861,7248,7990,6785,2149,6811,953,8226,8042,4792,2405,4272,3567,7683,1946,3368,2549,2907,4133,4720,1284,5325,527,7130,9537,9367,6900,2472,3887,8169,6755,2589,7275,2521,7802,5162,7889,588,1018,8901,8781,4086,7244,1384,2347,5554,2388,5179,8810,9521,487,8122,9780,6350,9340,4589,3929,1194,3119,5418,2716,547,9749,6099,9395,8069,9664,4941,3211,9900,7024,6297,5195,2235,7870,6972,1888,7062,2965,2698,4702,9193,1841,3252,6610,4303,4611,5449,9416,9019,2003,4218,771,3,6660,1605,4410,4384,595,6831,5506,8557,6510,3381,6455,5691,9123,1307,608,3670,4485,5834,3389,4776,8087,3489,8302,6909,2092,2555,453,7621,8170,1327,8627,1268,57,5637,1569,7919,8099,1595,8705,2171,5853,9563,3353,9922,1453,5342,9784,4049,9074,5292,5893,4530,7371,9072,3827,6709,3213,1847,1045,6668,5641,591,9995,4655,6842,9349,8111,237,3526,1725,9513,8326,4583,4771,4480,344,3919,3658,1469,1898,3260,668,8539,8198,2684,5827,7597,3681,3308,4528,6104,6238,2500,4998,3391,1078,8521,4558,7053,3872,3185,3978,1837,2486,7150,5942,5820,360,6008,4680,9825,5768,7054,8541,3400,2152,8979,1782,5262,9289,7274,1181,7573,8617,5982,1337,8151,8785,9118,6868,9621,4733,3245,6041,3298,1689,2170,7663,1444,38,8935,5216,9399,8193,2259,9889,2455,230,1637,7772,65,5564,7266,3894,5332,6288,8760,9517,5620,4686,2641,2738,5041,4979,1886,1420,9960,8876,5539,1727,3499,8243,5159,5278,707,8139,7156,7726,6725,2448,8373,8292,6443,1622,6184,5297,897,8678,2429,7589,9402,1197,2147,2531,8283,6650,3797,4226,2533,306,8833,9138,734,5451,3314,2594,9041,9918,5929,9530,6628,9091,3281,2988,7143,1567,4975,3691,2903,2201,7210,7163,8896,6560,9333,7871,3595,3761,5301,3176,3109,2,7572,9435,9770,2122,7884,4885,5101,7246,630,3685,7417,1107,8936,3174,6587,9754,9864,5804,6552,5659,7918,8686,2296,8044,5048,3498,6462,6402,2728,312,7359,8517,1547,8742,6146,4457,1370,9843,8654,8361,7895,6498,9767,6325,1087,1022,1095,5203,6532,8377,2420,2022,1739,7453,9032,6360,6017,9115,1198,8561,6894,9773,1799,8568,3016,9218,9604,4704,7231,2057,3697,6336,6488,5374,8390,7003,1033,9089,9068,7947,5160,9320,9109,3270,7263,1073,7344,4844,2482,7401,2540,9003,7479,4003,6999,8097,7262,374,6064,4311,977,2956,8095,2449,7705,9481,5797,4056,3208,9329,3506,8955,5205,1887,4525,8708,6848,7272,2506,8950,7661,2960,4172,1196,3212,6627,3355,84,9410,1723,9669,7382,3296,384,6865,8976,406,2507,6506,6976,7921,5222,2434,5428,6555,1699,2683,1088,1925,1960,2733,5416,1572,5905,4944,965,2534,2611,5148,9842,2260,3988,5420,7773,2566,3454,9567,8153,2073,3871,6676,9811,8890,5328,969,7785,4727,3790,5158,3976,9680,2799,5130,7100,9634,4949,3714,683,4210,429,8501,6494,3087,3189,9370,2100,4249,293,9429,7032,7450,6992,6073,9400,2189,5701,3951,7218,7326,1952,5098,850,4280,3520,7817,9519,3715,9064,1244,6330,4933,5111,9673,3517,8878,8274,6773,7959,1693,4178,7496,6446,5316,328,2924,1986,6362,9628,932,4993,2495,7731,2028,6740,4134,5345,5596,9595,1903,1233,7090,5872,763,6672,6951,4305,3147,2230,3629,9925,9388,6258,9769,1292,7814,9209,2796,541,8444,6432,3866,185,1529,470,8857,1679,9656,3228,4243,2266,8997,8076,6624,8755,4987,6092,5516,3977,7657,7743,9596,2096,3042,4761,1449,5615,2229,7580,5322,5920,6187,7754,6500,8055,4902,7164,5394,3596,7290,6542,7395,9582,2053,1666,4090,4875,5061,2197,4634,7133,7413,6192,8779,6196,2829,4743,2797,2551,681,1464,9080,5878,58,2934,2640,5970,7350,3583,3247,4982,8291,4456,2806,6853,1146,4642,5650,5050,8898,8020,8259,1643,240,471,7867,8630,923,8780,4535,9055,9653,4575,7864,5697,2750,917,3606,3086,7960,5172,5664,1410,2843,9458,343,1776,6102,9347,2687,9785,2470,4308,5700,216,2163,419,1798,5926,4594,3218,3468,9515,4156,7339,9200,6998,9404,1795,5517,239,336,1724,7166,7724,938,5561,4660,7086,5181,3879,3030,1850,887,7093,8183,7669,5299,5968,8891,5789,929,295,2383,4248,8457,885,3195,2226,2300,6750,2321,2297,2481,3950,1542,6191,3661,7567,1995,7916,3390,3505,4813,4391,8280,9571,6202,9265,5512,2598,86,4089,7188,1329,5772,5257,1277,8586,6675,4935,1426,9916,9581,146,3171,2247,7294,4076,282,1918,1417,2048,7110,9405,4881,2425,9272,6027,3001,7040,8920,435,1093,9439,4567,462,3382,3327,1386,4635,333,788,4966,7907,8815,7551,3339,3616,3958,4245,6580,7203,5721,5685,4001,8041,6023,400,3777,3159,2068,1969,3019,4904,8296,6918,3073,7381,5723,1053,2633,5565,3041,7764,8554,3757,4123,8307,5907,313,8963,379,5908,2527,2775,6278,6503,7196,5019,7847,741,9215,7872,1117,9173,7404,8892,3497,8956,5331,9166,6548,6478,5706,7140,3912,9306,8900,6790,7983,81,21,4119,3209,8431,601,6057,6731,3549,8874,6118,4605,2947,7472,8167,8397,2187,1845,1011,53,8049,6412,2043,8120,9136,4333,4494,9585,9738,6988,8165,8059,4638,9052,4491,308,9957,8824,7804,8659,7976,4403,8959,3562,8466,4130,852,5347,4029,9733,6719,6881,44,7811,7706,8455,307,9313,2153,7509,2788,63,8067,8477,8559,3886,5349,4694,7834,5616,7099,4355,3276,3038,414,9473,6869,1258,7025,1293,9584,2771,8749,795,853,8271,2227,6955,4940,8646,7474,7477,5705,2363,567,9946,3070,6220,9364,7698,3488,5545,1395,9239,6317,4746,6885,6593,482,5832,2130,9846,2016,5818,6744,1749,8178,846,1462,408,4901,3858,9686,3957,9511,7548,5284,8127,5073,9731,6345,398,1710,9779,5857,4538,220,9559,9317,4357,8716,4068,4956,8184,8590,1324,5930,3780,3198,9338,3244,114,6845,7974,8359,530,8652,7981,3980,3370,7961,2456,7769,9771,8906,450,7607,4734,7521,5966,4341,3481,2900,5548,629,9643,1433,4321,915,6524,7379,6882,6609,9168,1621,218,493,4985,4947,3917,2341,8284,1442,5206,2231,5147,7779,6517,483,7631,3525,204,3881,358,2944,4958,4203,5461,4990,402,193,1143,7523,5256,6003,5083,5264,688,6879,2126,7640,6856,1614,275,5856,8729,6221,73,375,4626,863,5998,423,7478,1691,6908,3267,2607,8338,8826,1630,1803,999,4310,750,9985,7941,5573,1758,7322,1701,5454,4350,2245,9574,128,9814,3789,8926,7638,751,4351,901,7170,4685,3326,944,3599,1970,1199,6952,7611,8086,4190,4860,325,7117,1653,4585,4464,6169,1736,4196,4677,3895,5475,2689,1086,4163,9648,4450,9278,3708,3556,5831,1638,4613,1528,5846,9245,7436,2088,279,9177,2908,4381,7361,2168,7298,3795,7562,2909,7563,276,5947,160,5552,5521,167,3110,7224,8330,9853,8100,2758,7503,2027,7179,6574,3805,5320,6913,8032,198,1932,9477,1849,8402,5344],[5344,6081]]))
